BST to Greater Sum Tree

Convert BST to Greater Sum Tree asks you to rewrite every node so it holds the sum of all values greater than or equal to it. The clean solution exploits the one thing a BST gives you for free: an ordering. A small twist on in-order traversal turns this into a single elegant pass.

The slow way first

The obvious idea: for each node, scan the entire tree and add up every value that is greater than or equal to it. That is O(n²) — a full traversal per node. We can do far better by noticing that a BST already stores its values in sorted order, so we never need to re-scan.

The question to ask: for a given node, which values are greater than it? In a BST, the answer is "everything to its right" — and an in-order walk visits values in ascending order. So if we walk in the reverse direction, we meet values from largest to smallest, and a single running total is all the bookkeeping we need.

The idea: reverse in-order with a running total

A normal in-order traversal goes left → node → right and yields values in increasing order. Flip it to right → node → left and you get values in decreasing order. Keep a total that we add each node's value to as we visit it; because we visit larger values first, total is always the sum of everything we have already seen — which is exactly the set of values greater than the current node. Assign total back into the node.

The key insight: by the time we reach a node, every value greater than it has already been folded into total, so one assignment is correct and final.

Walk through it

Step through the animation. We dive right to the largest value 7 and set total = 7. Backing out, 6 becomes 7 + 6 = 13, then its left child 5 becomes 18. We return to the root 4 for 22, then descend left to handle 2 (24) and finally 1 (25). One pass, smallest written last.

Pseudocode

total = 0
visit(node):
    if node is null: return
    visit(node.right)        # larger values first
    total = total + node.val # fold this node into the running sum
    node.val = total         # this node = sum of all values >= it
    visit(node.left)         # then the smaller values
visit(root)
return root

The Python solution

def bst_to_gst(root):
    total = 0
    def visit(node):
        nonlocal total
        if node is None:
            return
        visit(node.right)
        total += node.val
        node.val = total
        visit(node.left)
    visit(root)
    return root

• total is the running sum of every value visited so far — and since we go largest-first, that is every value greater than or equal to the current node.
• nonlocal total lets the inner visit mutate the accumulator defined in the outer function.
• visit(node.right) is the crucial reversal: we recurse right first so larger values are processed before the current node.
• total += node.val then node.val = total folds the node in and writes back the answer.
• visit(node.left) handles the smaller values last.

Complexity

The time drops from O(n²) to O(n) — we touch each node exactly once. The extra space is O(h) for the recursion stack, where h is the tree height (O(log n) for a balanced tree, O(n) in the worst case).

When this pattern shows up

Practice