Convert BST to Greater Tree — Solution in Python, Java & C++
Convert BST to Greater Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Convert BST to Greater Tree is a medium coding problem on depth-first search, binary search and trees, asked in Amazon and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Binary Search, Trees
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree whose values are all distinct. Turn it into a greater tree: replace every node's value with the sum of its original value and all values in the tree that are greater than it. Keep the tree's shape and return its root.
Example 1
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Explanation: The largest value, 8, stays 8; 7 becomes 7 + 8 = 15; 6 becomes 6 + 7 + 8 = 21; and so on down to 0, which becomes the sum of every value, 36.
Example 2
Input: root = [0,null,1]
Output: [1,null,1]
Explanation: 1 has nothing greater and stays 1; 0 becomes 0 + 1 = 1.
Example 3
Input: root = []
Output: []
Explanation: An empty tree stays empty.
Constraints
The number of nodes in the tree is in the range [0, 10^4]-10^4 <= Node.val <= 10^4All the values in the tree are uniqueroot is guaranteed to be a valid binary search tree
Hints for Convert BST to Greater Tree
Hint 1
Which nodes are greater than a given node? In a search tree, they are exactly the ones an in-order walk visits after it.
Hint 2
Walk the tree in reverse in-order — right subtree, node, left subtree — so the nodes come largest first.
Hint 3
Keep one running total across the whole walk: add each node's value to it, then write the total back into the node.
How to solve Convert BST to Greater Tree
An in-order walk of a BST lists values in increasing order, so the reverse walk (right, node, left) lists them in decreasing order. A running sum along that walk is, at each node, the sum of that node and everything greater.
Approach
- Keep an accumulator
acc = 0shared by the whole walk. - Visit a node: first recurse into its right subtree.
- Then add the node's value to
accand set the node's value toacc. - Then recurse into its left subtree. Return the root when the walk ends.
Why it works
When a node is reached in reverse in-order, every node with a greater value has already been visited and added to acc, and no smaller one has. So acc + node.val is exactly the required sum.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion, h being the tree's height
Pitfalls
- The accumulator must persist across recursive calls — pass it by reference or keep it outside the recursion.
- Add the node's original value before overwriting it; the overwritten value is the new total.
- Going left first produces sums of smaller values instead.
Reference solution
Python
from typing import Optional
def convertBST(root: Optional[TreeNode]) -> Optional[TreeNode]:
acc = 0
stack = []
node = root
while node is not None or stack:
while node is not None:
stack.append(node)
node = node.right
node = stack.pop()
acc += node.val
node.val = acc
node = node.left
return rootJava
public static TreeNode convertBST(TreeNode root) {
int acc = 0;
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.right;
}
node = stack.pop();
acc += node.val;
node.val = acc;
node = node.left;
}
return root;
}C++
void greaterWalk(TreeNode* node, int& acc);
TreeNode* convertBST(TreeNode* root) {
int acc = 0;
greaterWalk(root, acc);
return root;
}
void greaterWalk(TreeNode* node, int& acc) {
if (!node) return;
greaterWalk(node->right, acc);
acc += node->val;
node->val = acc;
greaterWalk(node->left, acc);
}JavaScript
var convertBST = function(root) {
var acc = 0, stack = [], node = root;
while (node !== null || stack.length > 0) {
while (node !== null) {
stack.push(node);
node = node.right;
}
node = stack.pop();
acc += node.val;
node.val = acc;
node = node.left;
}
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Search