Binary Search Tree to Greater Sum Tree
A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 1
- Core for
- 2 roles
The problem
Given the root of a binary search tree, convert it to a greater sum tree where each node's value is replaced by the sum of all values greater than or equal to that node's value in the original tree.
Example 1
- Input
- [5,2,8,1,3,null,9]
- Output
- [22,27,17,28,25,null,9]
- Why
- Each node becomes itself plus everything larger: 8 turns into 8+9=17, 5 into 5+8+9=22, and so on.
Example 2
- Input
- [2,null,6]
- Output
- [8,null,6]
- Why
- 6 stays 6; 2 becomes 2+6=8.
Example 3
- Input
- [1,0,2]
- Output
- [3,3,2]
- Why
- Node 0 becomes 0+1+2=3, node 1 becomes 1+2=3, node 2 stays 2.
Constraints
- The number of nodes is in the range [1, 104].
- 0 <= Node.val <= 100
- All values are unique.
How to think about it
Updated 2026-09-29Every node needs the sum of all values greater than or equal to itself. Standard inorder visits from smallest to largest, which is the wrong direction; reversing the visit order to right-root-left processes elements from largest to smallest. In that order, a single running sum accumulator carries everything each node needs.
Approaches, worst first
Inorder collect and suffix prefix array
time O(n) · space O(n)
Flatten the BST into a sorted array, compute prefix sums from the right, and perform a second tree pass to overwrite values from a hash table lookup. Correct, but wastes extra passes and auxiliary memory.
Reverse inorder recursion
time O(n) · space O(h)
Traverse right subtree, update running sum with current node value, overwrite current value with the running sum, and traverse left subtree. Visits each node once with stack depth bounded by tree height.
Reverse Morris traversalWrite this one
time O(n) · space O(1)
Establish temporary threads from each node's inorder successor back to the node to traverse in descending order without a stack. Updates the running accumulator in-place while achieving strictly constant extra memory.
Where people lose marks · 2
- Accumulating after overwriting. If you overwrite `node.val = sum` before adding the original value to `sum`, the running total double-counts or corrupts subsequent nodes.
- Traversing left before right. Standard inorder gives ascending order; updating with an accumulator during standard inorder computes smaller-or-equal sums instead of greater.
Full solution
C++
#include <bits/stdc++.h>
using namespace std;
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };
TreeNode* bstToGst(TreeNode* root) {
int sum = 0;
stack<TreeNode*> st;
TreeNode* curr = root;
while (!st.empty() || curr != nullptr) {
while (curr != nullptr) {
st.push(curr);
curr = curr->right;
}
curr = st.top();
st.pop();
sum += curr->val;
curr->val = sum;
curr = curr->left;
}
return root;
}
Java
import java.util.*;
public class Main {
static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }
static TreeNode bstToGst(TreeNode root) {
int sum = 0;
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
stack.push(curr);
curr = curr.right;
}
curr = stack.pop();
sum += curr.val;
curr.val = sum;
curr = curr.left;
}
return root;
}
}
Python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bst_to_gst(root):
curr_sum = 0
def dfs(node):
nonlocal curr_sum
if not node:
return
dfs(node.right)
curr_sum += node.val
node.val = curr_sum
dfs(node.left)
dfs(root)
return root
JavaScript
function TreeNode(val, left, right) {
this.val = val;
this.left = left || null;
this.right = right || null;
}
function bstToGst(root) {
let sum = 0;
let curr = root;
const stack = [];
while (stack.length || curr) {
while (curr) {
stack.push(curr);
curr = curr.right;
}
curr = stack.pop();
sum += curr.val;
curr.val = sum;
curr = curr.left;
}
return root;
}
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .