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:
[0, 104].-104 <= Node.val <= 104root is guaranteed to be a valid binary search tree.Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
In #538 Convert BST to Greater Tree, each node in a Binary Search Tree must be updated so that its value becomes the original value plus the sum of all greater values in the tree. The key observation comes from the BST property: an in-order traversal visits nodes in ascending order. If we reverse this traversal (right → node → left), we process nodes from the largest to the smallest.
Using a Depth-First Search (DFS) with reverse in-order traversal allows us to maintain a running cumulative sum of visited nodes. As each node is visited, we update its value using the accumulated sum before moving to smaller nodes. This approach ensures that when a node is processed, all greater values have already been accounted for.
The traversal visits every node exactly once, giving an efficient linear solution. Because recursion or an explicit stack is used for DFS, the extra memory depends on the height of the tree.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Reverse In-order DFS Traversal | O(n) | O(h) |
NeetCode
This approach leverages the property of Binary Search Trees where the nodes in the right subtree are greater than those in the left subtree. By performing a reverse inorder traversal (right -> root -> left), we can accumulate the sum of all nodes greater than the current node and update each node with this accumulated sum. The traversal ensures that we always process the greater nodes first.
Time Complexity: O(n), where n is the number of nodes in the BST, since we visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack used during traversal.
1#include <stdio.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode
The C solution defines a helper function traverse that modifies the tree in place. This function is called with the root of the tree and maintains a running total of the sum of node values. We first recurse into the right subtree (greater values), add the current node's value to the sum, update the node's value to the sum, and finally recurse into the left subtree.
The Morris Traversal technique allows in-order traversal of a binary tree without using extra space for recursion or a stack. It modifies the tree structure during the traversal, and at the end of the traversal, the original tree structure is restored.
For this problem, we adapt the Morris Traversal to traverse the tree in reverse inorder fashion and keep track of the sum of nodes greater than the current node.
Time Complexity: O(n), where n is the number of nodes. Although every edge is visited at most twice, the overall complexity remains linear.
Space Complexity: O(1) since no extra space is used apart from variables.
1class TreeNode:
2 def __init__(self, val=0,
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
Yes, variations of this problem appear in technical interviews at major tech companies. It tests understanding of BST properties, tree traversal strategies, and how to maintain state during DFS.
In a BST, in-order traversal produces values in ascending order. Reversing the order processes nodes from largest to smallest, which means by the time you reach a node, you have already seen all greater values and can add their sum directly.
The optimal approach is a reverse in-order traversal (right → node → left). Since a BST visited this way processes nodes from largest to smallest, you can maintain a running sum and update each node as you traverse. This ensures all greater values are already included when modifying a node.
A Binary Search Tree combined with Depth-First Search is ideal for this problem. Using recursion or an explicit stack helps perform reverse in-order traversal efficiently while maintaining a cumulative sum of visited nodes.
This Python solution uses the Morris Traversal technique, which allows modifying the tree without using stack or recursion explicitly. The key idea is to establish a temporary link between each node and its inorder predecessor, traverse in reverse inorder, update the nodes, and then restore the tree structure by removing the temporary links.