Binary Search Tree to Greater Sum Tree

Given the root of a Binary Search Tree (BST), convert it to a Greater Sum Tree where every node's new value equals the original value plus the sum of all values greater than it in the original BST.

This is LeetCode 1038: Binary Search Tree to Greater Sum Tree. You are given a BST and need to modify it in-place so that each node holds the sum of all node values that are greater than or equal to the original node value.

Example: For the BST [4, 1, 6, null, null, 5, 7], node 7 stays 7 (nothing is greater), node 6 becomes 13 (6+7), node 5 becomes 18 (5+6+7), node 4 becomes 22 (4+5+6+7), and node 1 becomes 23 (1+4+5+6+7).

Why this problem matters

This problem tests whether you truly understand the ordering property of a BST. In a BST, an inorder traversal (left, root, right) visits nodes in ascending order. Reverse that to right, root, left, and you visit nodes in descending order. That descending visit order is exactly what you need: by the time you reach a node, you have already seen every value greater than it, and your running sum holds their total.

Key insight

A BST's inorder traversal gives you nodes in sorted order. If you reverse that traversal (visit right subtree first, then root, then left subtree), you process nodes from largest to smallest. Keep a running sum as you go. When you visit a node, add its original value to the sum, then set the node's value to that sum. Because you have already processed every node with a larger value, the sum naturally includes all values greater than the current node.

You do not need to search the tree for larger values. You do not need any extra data structure. A single reverse inorder pass handles everything.

Walking through step by step

Let's trace through the BST [4, 1, 6, null, null, 5, 7] and watch the reverse inorder traversal update each node.

Notice how the running sum only ever increases. Each node gets the sum of itself plus everything already processed, which is exactly the set of nodes with values greater than or equal to it. The BST property guarantees this ordering.

The solution

def bstToGst(root):
    total = 0
    def reverse_inorder(node):
        nonlocal total
        if not node:
            return
        reverse_inorder(node.right)
        total += node.val
        node.val = total
        reverse_inorder(node.left)
    reverse_inorder(root)
    return root

Here is what each piece does:

• total = 0 is the running sum that accumulates values from largest to smallest.
• reverse_inorder(node.right) processes the right subtree first, ensuring all larger values are summed before the current node.
• total += node.val adds the current node's original value to the running sum.
• node.val = total replaces the node's value with the accumulated sum (original value plus all greater values).
• reverse_inorder(node.left) then processes the left subtree, where all values are smaller than the current node.
• The function modifies the tree in-place and returns the root.

Iterative alternative

If you prefer to avoid recursion, you can use an iterative reverse inorder traversal with an explicit stack:

def bstToGst(root):
    total = 0
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.right
        node = stack.pop()
        total += node.val
        node.val = total
        node = node.left
    return root

The iterative version follows the same logic. Push nodes while going right, pop to process, then move left. The running sum accumulates identically.

Complexity analysis

Time is O(n) where n is the number of nodes. You visit every node exactly once and do O(1) work at each node (one addition and one assignment).

Space is O(h) where h is the height of the tree. The recursive version uses O(h) stack frames. The iterative version uses an explicit stack that holds at most O(h) nodes. For a balanced BST, h = log n. For a skewed tree, h = n.

Building blocks

This problem combines two fundamental patterns:

1. Reverse inorder traversal. Standard inorder goes left, root, right and visits BST nodes in ascending order. Reversing it to right, root, left visits nodes in descending order. This is the key technique whenever you need to process BST nodes from largest to smallest. The traversal structure is identical to normal inorder, you just swap which child you visit first.

2. Running sum accumulation. You maintain a single variable that grows as you traverse. Each node reads and updates this variable. The pattern appears in prefix sum problems, but here it is applied to a tree traversal instead of an array. The crucial detail is that the traversal order determines what the sum contains at each step.

Edge cases

• Single node. The tree has one node. Its greater sum is just itself (no values are greater). The running sum adds its value and assigns it back. The output equals the input.
• Left-skewed tree (descending chain). Every node only has a left child. The reverse inorder visits the root first (the largest), then works down. The running sum grows with each step. This is the worst case for space at O(n) stack depth.
• Right-skewed tree (ascending chain). Every node only has a right child. The reverse inorder goes all the way to the rightmost (largest) node first, then works back up. Same O(n) space worst case.
• All nodes have the same value. Each node's new value becomes (original value) times (its position in reverse inorder + 1 relative count). For example, three nodes all with value 5: they become 5, 10, 15 from right to left.
• Two nodes. Root and one child. If the child is on the right, it is larger, so it stays the same and the root becomes root + child. If the child is on the left, the root stays the same and the child becomes child + root.

From understanding to recall

You just traced how reverse inorder traversal naturally visits BST nodes from largest to smallest, and how a running sum turns that ordering into the exact transformation the problem asks for. The entire solution is three lines inside a recursive helper: go right, accumulate and assign, go left.

But will you remember to reverse the inorder direction under interview pressure? Will you remember that nonlocal total is needed to update the outer variable from the nested function? Will you instinctively reach for reverse inorder when a BST problem mentions "greater values"?

Spaced repetition builds that recall. You type the solution from scratch at increasing intervals: after a day, then three days, then a week. Each time, you reconstruct the reverse inorder helper, the running sum, and the in-place update from memory. After a few rounds, the pattern becomes automatic.

Reverse inorder traversal with a running accumulator is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Convert BST to Greater Tree - The same problem with different constraints
• Binary Tree Inorder Traversal - The base traversal pattern this builds on
• Kth Smallest Element in a BST - Another problem leveraging BST inorder properties

CodeBricks breaks problems like Binary Search Tree to Greater Sum Tree into the building blocks behind them, then uses spaced repetition to make those blocks automatic. If you want to stop re-solving the same patterns and start recognizing them on sight, give it a try.