This problem requires updating each node in a BST so it reflects its original value plus all values greater than it. The most efficient solution leverages a reverse in-order DFS traversal, maintaining a running sum of visited nodes. By processing nodes from largest to smallest, the algorithm ensures each node is incremented correctly without extra space for storing node values.
Problem Statement
Given a Binary Search Tree (BST), transform it into a Greater Sum Tree where each node's new value is equal to its original value plus the sum of all values in the BST that are greater than it. The BST property ensures in-order traversal yields nodes in ascending order, which is crucial for tracking cumulative sums.
Implement an in-place transformation without changing the BST structure. For example, given root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8], the resulting Greater Sum Tree should be [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]. Constraints include 1 <= nodes <= 100, 0 <= Node.val <= 100, and all node values are unique.
Examples
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 details omitted.
Example 2
Input: root = [0,null,1]
Output: [1,null,1]
Example details omitted.
Constraints
- The number of nodes in the tree is in the range [1, 100].
- 0 <= Node.val <= 100
- All the values in the tree are unique.
Solution Approach
Reverse In-Order Traversal with Running Sum
Traverse the BST in reverse in-order (right, root, left) to process nodes from largest to smallest. Maintain a cumulative sum variable that adds the current node's value before updating it. This approach ensures each node receives the sum of all greater values naturally during traversal.
Recursive DFS Implementation
Use a recursive helper function that updates the running sum at each node. The recursion first visits the right subtree, updates the node's value with the cumulative sum, then proceeds to the left subtree. This method leverages the call stack for traversal state without additional data structures.
Iterative DFS Using Stack
An alternative is to use an explicit stack to simulate reverse in-order traversal iteratively. Push nodes while traversing right, pop to update values and cumulative sum, then move to the left child. This avoids recursion depth issues while maintaining the same sum-tracking logic.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Time complexity is O(n) since each node is visited exactly once. Space complexity is O(1) if ignoring recursion stack or O(h) with recursive DFS, where h is the tree height. The in-place update avoids extra arrays for storing node values.
What Interviewers Usually Probe
- Expect a clear reverse in-order DFS approach that handles cumulative sums correctly.
- Watch for correct in-place updates without changing tree structure.
- Demonstrate understanding of BST properties and traversal order impact.
Common Pitfalls or Variants
Common pitfalls
- Traversing in standard in-order instead of reverse, which miscalculates cumulative sums.
- Resetting the running sum incorrectly between recursive calls or iterations.
- Using extra space unnecessarily to store node values instead of updating in-place.
Follow-up variants
- Convert a BST to a Lesser Sum Tree by accumulating all smaller node values using in-order traversal.
- Handle BSTs with duplicate values where the greater-sum rule includes duplicates differently.
- Implement the transformation iteratively using Morris traversal to achieve O(1) extra space.
How GhostInterview Helps
- Guides the reverse in-order DFS traversal pattern and running sum logic for this exact BST problem.
- Highlights failure modes like incorrect traversal order or mismanaged cumulative sums.
- Provides structured walkthroughs with step-by-step node updates to confirm Greater Sum Tree correctness.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What traversal method should I use for Binary Search Tree to Greater Sum Tree?
Reverse in-order traversal ensures nodes are processed from largest to smallest, enabling correct accumulation of greater values.
Can I modify the BST in place for this problem?
Yes, the transformation is designed to be in-place without altering the tree's structure, just updating node values.
What if the BST has only one node?
A single node remains unchanged in value since there are no greater nodes to add.
Is recursion required to solve this problem?
Recursion is common but an iterative stack-based reverse in-order traversal works equally well.
How does GhostInterview help with this pattern?
It provides targeted guidance on reverse in-order traversal, running sum tracking, and typical pitfalls specific to the Greater Sum Tree pattern.
Need direct help with Binary Search Tree to Greater Sum Tree instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Binary Search Tree to Greater Sum Tree from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given a BST and a range, calculate the sum of all node values within that range.
Open problem page#897 Increasing Order Search TreeRearrange a binary search tree so all nodes follow increasing order with only right children using in-order traversal.
Open problem page#783 Minimum Distance Between BST NodesFind the minimum difference between values of two different nodes in a Binary Search Tree using tree traversal and state tracking.
Open problem page