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 <= 100Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/
The key observation in Binary Search Trees (BST) is that an in-order traversal processes nodes in ascending order. To convert the tree into a Greater Sum Tree, each node must be updated with the sum of all node values greater than or equal to it. A smart way to achieve this is by performing a reverse in-order traversal (right → node → left). This traversal visits nodes from largest to smallest.
While traversing, maintain a running cumulative sum of the values seen so far. When visiting a node, add its value to the running sum and update the node with this new total. This ensures every node includes the sum of all greater values already processed.
The approach naturally fits a Depth-First Search (DFS) recursion pattern, though it can also be implemented iteratively with a stack. Because each node is visited once, the method is efficient and leverages the sorted property of BSTs.
Time Complexity: O(n) since each node is processed once.
Space Complexity: O(h) due to recursion stack where h is the tree height.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Reverse In-Order DFS Traversal | O(n) | O(h) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
What traversal method organizes all nodes in sorted order?
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.
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.
1#include<stdio.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In a BST, reverse in-order traversal processes nodes from largest to smallest. This order allows us to accumulate the sum of greater values first, making it easy to update each node correctly.
Yes, BST transformation problems like this frequently appear in technical interviews. They test understanding of tree traversal patterns, recursion, and how to leverage BST properties for efficient solutions.
The optimal approach uses a reverse in-order traversal of the BST (right, node, left). This visits nodes in descending order and maintains a running sum to update each node with the total of all greater or equal values.
Depth-First Search with recursion is commonly used because it naturally supports reverse in-order traversal. An iterative approach using a stack can also simulate the same traversal order if recursion is not preferred.
The JavaScript implementation emphasizes an iterative solution using an array as a stack. This approach follows the ordered handling similar to recursion, facilitating value changes on an iterative basis.