Convert BST to Greater Tree — LC 538 Reverse In-Order Pattern

Problem Statement#

Given the root of a Binary Search Tree, convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in the BST.

Constraints:

• The number of nodes is in the range [0, 10^4]
• -10^4 <= Node.val <= 10^4
• All values are unique
• Given tree is a valid BST

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]

Input:  root = [0,null,1]
Output: [1,null,1]

Why This Problem Matters#

LeetCode 538 Convert BST to Greater Tree (also known as LC 1038 Binary Search Tree to Greater Sum Tree) is asked at Google, Microsoft, Amazon, and Apple. It is the canonical "exploit BST ordering with reverse in-order" question. Candidates who immediately see that a reverse in-order traversal visits nodes in descending order — and that a running suffix sum is therefore trivial — earn the optimal solution in three lines.

Interviewers love this problem because it elegantly tests two skills: (1) deep understanding that in-order on a BST yields sorted ascending order, and (2) creative direction reversal to get descending order. The pattern reappears in problems like Kth Largest Element in BST, Range Sum BST descending, and BST Iterator (reverse).

This is a frequent Google phone screen and Amazon onsite warmup.

The Core Insight#

In-order traversal of a BST visits nodes in ascending order. Reverse in-order (right -> root -> left) visits them in descending order. While walking in descending order, we accumulate a running sum. When we visit a node, we replace its value with the running sum (which already includes itself plus all larger nodes seen so far).

The trick: do sum += node.val BEFORE assigning node.val = sum, so the node includes its own original value in its new value (per problem spec, the converted value = original key + sum of all greater keys, which equals running sum of all nodes seen so far in descending order).

This gives a single O(n) pass with O(h) recursion space, beating any sort-and-suffix-sum alternative.

Visual Dry Run#

Tree: [2,1,3]

    2
   / \
  1   3

Reverse in-order: 3, 2, 1.

Result: [5,6,3].

Solution (Optimal)#

class Solution:
    def convertBST(self, root):
        self.total = 0
        def reverse_inorder(node):
            if not node:
                return
            reverse_inorder(node.right)
            self.total += node.val
            node.val = self.total
            reverse_inorder(node.left)
        reverse_inorder(root)
        return root

var convertBST = function(root) {
    let total = 0;
    const dfs = (node) => {
        if (!node) return;
        dfs(node.right);
        total += node.val;
        node.val = total;
        dfs(node.left);
    };
    dfs(root);
    return root;
};

Time: O(n) — every node visited once. Space: O(h) — recursion stack depth equals tree height.

Common Mistakes#

• Doing forward in-order — produces ascending sums, opposite of what we need.
• Two-pass solution: collect values, sum them, reassign — works but doubles time and uses O(n) space.
• Using a global variable inadvertently shared across test cases (in some test harnesses).
• Recursing left first — same as forward in-order, wrong direction.
• Forgetting the return root at the end — modifies in place but interview expects return.

Interview Tips#

• Say out loud: "BST in-order is sorted ascending; I'll reverse it for descending and accumulate."
• Draw a 3-node tree and trace the recursion to convince yourself of the order.
• Mention space: O(h) recursion stack, O(1) extra besides the running sum.
• If asked iterative, use a stack with right-first pushes — Morris traversal achieves O(1) space.

Follow-up Questions#

• Iterative without recursion? Stack-based reverse in-order with O(h) space.
• O(1) space? Morris reverse-in-order traversal using right threading.
• Handle duplicates? Problem assumes unique values; with duplicates clarify whether equal keys are "greater than" each other.
• Return new tree without modifying original? Build a parallel tree during traversal.
• Generalize to any binary tree (not BST)? Sort values, build a hashmap of value -> suffix-sum, then DFS rewrite.

Key Takeaways#

• LeetCode 538 is a Medium-difficulty FAANG BST question asked at Google, Microsoft, and Amazon.
• The optimal pattern is reverse in-order traversal: right -> root -> left.
• Reverse in-order on a BST visits nodes in strictly descending order — perfect for suffix sums.
• Maintain a running total that accumulates as you visit each node.
• Time complexity is O(n), space complexity is O(h) for the recursion stack.
• Morris traversal can reduce space to O(1) at the cost of mutating tree pointers.
• The pattern transfers to LC 1038, Kth Largest in BST, and reverse BST iterators.