Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
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]
Example 2:
Input: root = [0,null,1] Output: [1,null,1]
Constraints:
[1, 100].0 <= Node.val <= 100
Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/
Problem Overview: You are given a binary search tree where each node must be updated so its new value equals the original value plus the sum of all keys greater than it. The structure of the tree stays the same; only node values change.
Approach 1: Reverse In-Order Traversal (DFS) (Time: O(n), Space: O(h))
A BST visited in reverse in-order order (right → node → left) processes nodes from largest to smallest. Maintain a running variable sum that stores the cumulative total of nodes already visited. When you reach a node, add its value to sum and update the node with this new total. Because nodes are visited in descending order, sum always represents the sum of all greater values. This approach relies on depth-first search and the ordering property of a BST. The recursion depth equals the tree height h, giving O(h) auxiliary space. For balanced trees this is O(log n), while a skewed tree degrades to O(n).
The key insight is exploiting the BST ordering. Instead of computing greater sums by scanning other nodes, you accumulate them naturally while traversing from the largest value downward. This produces an optimal linear-time solution and minimal extra state.
Approach 2: Iterative Traversal Using a Stack (Time: O(n), Space: O(h))
The same reverse in-order logic can be implemented iteratively with an explicit stack. Start from the root and push nodes while moving right to reach the maximum element. Pop a node, update the running sum, modify the node value, then move to its left subtree. Repeat the process until the stack becomes empty. Each node is pushed and popped once, keeping the time complexity O(n).
This approach avoids recursion and is useful in environments where stack depth is a concern. The stack stores at most the height of the tree, so space complexity remains O(h). The algorithm still leverages the sorted property of a binary tree structured as a BST, ensuring nodes are processed in descending order.
Recommended for interviews: Reverse in-order traversal is the expected solution. It demonstrates understanding of BST ordering and how DFS traversal patterns can transform data efficiently. Mentioning the iterative stack variant shows awareness of recursion limits and gives a practical alternative while keeping the same O(n) performance.
A reverse in-order traversal (right-root-left) allows us to visit nodes in decreasing order of their values in a BST. By maintaining a cumulative sum during this traversal, we can update each node with the sum of all nodes that have been visited so far, effectively converting it into a Greater Sum Tree.
This C solution uses a helper function to perform reverse in-order traversal on the BST. As it visits each node, it maintains a cumulative sum of values, updating each node with this cumulative sum. This effectively transforms the BST into a Greater Sum Tree.
The time complexity is O(n) where n is the number of nodes, as each node is visited once. The space complexity is O(h), where h is the height of the tree, representing the stack space used by the recursion.
We can emulate the recursive reverse in-order traversal with an iterative approach using a stack. By processing the nodes in decreasing order of their values, we maintain a sum of all visited nodes and update each node accordingly.
This C solution uses an explicit stack data structure to simulate the recursive reverse in-order traversal process. The sum is accumulated for nodes observed, and their values are updated iteratively.
The time complexity is O(n) because each node is visited once in the traversal loop. Space complexity is O(h) for stack use in the case where the tree's height is h.
Traverse the binary search tree in the order of "right-root-left". Accumulate all the node values encountered into s, and assign the accumulated value to the corresponding node.
Time complexity is O(n), and space complexity is O(n), where n is the number of nodes in the binary search tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
Morris traversal does not require a stack, with a time complexity of O(n) and a space complexity of O(1). The core idea is as follows:
Define s as the cumulative sum of the node values in the binary search tree. Traverse the binary tree nodes:
root is null, add the current node value to s, update the current node value to s, and move the current node to root.left.root is not null, find the leftmost node next in the right subtree (i.e., the successor node of root in an in-order traversal):next is null, set the left subtree of next to point to the current node root, and move the current node to root.right.next is not null, add the current node value to s, update the current node value to s, then set the left subtree of next to null (i.e., remove the link between next and root), and move the current node to root.left.Morris reverse in-order traversal follows the same idea as Morris in-order traversal, except that the traversal order changes from "left-root-right" to "right-root-left".
| Approach | Complexity |
|---|---|
| Reverse In-Order Traversal | The time complexity is |
| Iterable Approach Using a Stack | The time complexity is |
| Recursion | — |
| Morris Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse In-Order Traversal (DFS) | O(n) | O(h) | Preferred solution for BST problems; simple and optimal when recursion depth is manageable. |
| Iterative Traversal Using Stack | O(n) | O(h) | Useful when avoiding recursion or when stack overflow risk exists for deep trees. |
Binary Search Tree to Greater Sum Tree | Brute | Better | Optimal | Leetcode 1038 | codestorywithMIK • codestorywithMIK • 9,286 views views
Watch 9 more video solutions →Practice Binary Search Tree to Greater Sum Tree with our built-in code editor and test cases.
Practice on FleetCode