Convert BST to Greater Tree: Reverse Inorder Traversal

You are given the root of a binary search tree. Convert it to a Greater Tree where every node's new value equals its original value plus the sum of all values greater than it in the original BST.

This is LeetCode 538: Convert BST to Greater Tree, a medium problem that tests whether you can think about BST traversal order in a creative way. The trick is realizing that one specific traversal order gives you exactly what you need.

The problem

Given a BST, replace each node's value with the sum of all values that are greater than or equal to that node's original value. The tree structure stays the same, only the values change.

For example, in a BST with values [0, 1, 2, 4, 5, 6, 7], the largest node (7) stays 7 because nothing is greater. Node 6 becomes 6 + 7 = 13. Node 4 becomes 4 + 5 + 6 + 7 = 22. The smallest node (0) becomes the total sum of the entire tree.

The key insight

In a BST, an inorder traversal (left, node, right) visits nodes in ascending order. If you reverse that, doing right, node, left, you visit nodes from largest to smallest. That is exactly the order you need.

Keep a running sum as you traverse. At each node, add the node's value to the running sum, then replace the node's value with the running sum. Because you are visiting from largest to smallest, the running sum at any point is the sum of all values greater than or equal to the current node.

The solution

def convert_bst(root):
    total = 0

    def traverse(node):
        nonlocal total
        if node is None:
            return
        traverse(node.right)
        total += node.val
        node.val = total
        traverse(node.left)

    traverse(root)
    return root

Step-by-step walkthrough

Let's trace through the tree [4, 1, 6, 0, 2, 5, 7] using reverse inorder traversal. Watch how the running sum grows as we visit nodes from largest to smallest.

Notice the pattern: each node's new value is simply the running sum after adding its original value. Because we visit from right to left, the running sum always contains exactly the values that are greater than or equal to the current node.

Complexity analysis

Time: O(n) because we visit every node exactly once and do O(1) work at each node (one addition and one assignment).

Space: O(h) where h is the height of the tree, due to the recursion stack. For a balanced BST, h = log n. For a completely skewed tree, h = n.

The building blocks

1. Reverse inorder traversal

Standard inorder (left, node, right) gives you sorted order in a BST. Reversing it to (right, node, left) gives you reverse sorted order. This is useful any time you need to process BST nodes from largest to smallest. The recursive structure is identical to regular inorder, you just swap which child you visit first.

2. Running sum accumulation

Instead of computing the sum of all greater values from scratch for each node (which would be O(n) per node, O(n^2) total), you carry a single running sum through the traversal. Each node adds its value to the sum and then uses that sum as its new value. This reduces the work to O(1) per node.

Edge cases

• Single node tree: the node's value stays the same, since no other values exist in the tree and the sum of values >= itself is just itself
• Left-skewed tree (descending chain): reverse inorder visits from root down, the running sum grows with each step
• Right-skewed tree (ascending chain): reverse inorder visits from the bottom up, the leaf keeps its value and each parent accumulates more
• Tree with negative values: the algorithm works the same way, the running sum can decrease when adding negative values

From understanding to recall

You just traced through a reverse inorder traversal and saw how a single running sum variable converts an entire BST into a Greater Tree. The core idea, visiting nodes from largest to smallest and accumulating as you go, is elegant and efficient.

But recognizing this pattern under interview pressure is harder than understanding it now. The connection between "sum of all greater values" and "reverse inorder" is not obvious until you have drilled it a few times. Spaced repetition helps you internalize the link between the problem shape and the traversal order, so that when you see a similar problem, the approach comes to mind automatically.

Related posts

• Validate Binary Search Tree - Another problem where the BST property and inorder traversal are the key insight
• Binary Tree Inorder Traversal - The foundational traversal pattern that this problem reverses
• Kth Smallest Element in a BST - Uses inorder traversal to find elements by their sorted position in a BST