Convert BST to Greater Tree
Medium · Trees · Tree · Depth-First Search · Binary Search Tree · Binary Tree
Problem
Given the root of a binary search tree with unique values, convert it into a Greater Tree and return its root.
In a Greater Tree, every node's new value is its original value plus the sum of all original values greater than it in the tree. The shape of the tree does not change. The tree may be empty (shown as []).
Examples
Input: root = [5,2,8,1,3,None,9] Output: [22,27,17,28,25,None,9]
9 has nothing larger; 8 becomes 17; 5 becomes 5 + 8 + 9 = 22; and so on down to 1, which becomes 28.
Input: root = [0,None,4] Output: [4,None,4]
4 stays 4, and 0 becomes 0 + 4.
Input: root = [-2,-5,3] Output: [1,-4,3]
3 stays 3; -2 becomes 1; -5 becomes -4.
Constraints
- The number of nodes is in the range [0, 10^4]
- -10^4 <= Node.val <= 10^4
- All values are unique
- root is a valid binary search tree
Approaches
- Baseline: add up the larger values for every node — time O(n^2), space O(n)
Follow-up
The running sum works because the walk meets the values in sorted order. The use cases run it the other way (each node gains all smaller values, plain in-order), and answer "sum of the values at least x" for thresholds that are not in the tree, with suffix sums and binary search.
Related problems
Start free on Cariara · Coding problems · System design studio
