Binary Search Tree to Greater Sum Tree

Binary Search Tree to Greater Sum Tree

What is this problem about?

The "Binary Search Tree to Greater Sum Tree interview question" is a transformation problem. You are given the root of a Binary Search Tree (BST). Your goal is to modify the tree so that every node's value is replaced with the sum of all values in the original tree that were greater than or equal to that node's value. Because it's a BST, "greater values" are always located to the right of any given node.

Why is this asked in interviews?

Companies like Microsoft and Amazon ask the "Binary Search Tree to Greater Sum Tree coding problem" to test a candidate's understanding of Tree Traversal and the inherent properties of BSTs. It evaluates if you can manipulate a tree in-place and if you recognize that a specific type of traversal—Reverse In-order Traversal—visits nodes in descending order, which is perfect for maintaining a running sum.

Algorithmic pattern used

This problem follows the Reverse In-order Traversal (Right-Root-Left) pattern.

1. Global/Shared Sum: Maintain a variable running_sum (initially 0).
2. Traversal:
   • Recursively visit the Right subtree. (These are the largest values).
   • Process the Root: Add the current node's value to the running_sum, then update the node's value to the current running_sum.
   • Recursively visit the Left subtree. (These values will now include the sum of everything to their right). This ensures each node is updated exactly once in $O(N)$ time.

Example explanation

BST: 4 is root, 1 is left, 6 is right.

1. Visit Right (6): running_sum = $0 + 6 = 6$. Node 6 becomes 6.
2. Visit Root (4): running_sum = $6 + 4 = 10$. Node 4 becomes 10.
3. Visit Left (1): running_sum = $10 + 1 = 11$. Node 1 becomes 11. Resulting Tree Values: 10 (root), 11 (left), 6 (right).

Common mistakes candidates make

• Naive Summation: For every node, performing a full traversal to find all greater nodes. This results in $O(N^2)$ complexity.
• Incorrect Traversal Order: Using a standard In-order (Left-Root-Right), which visits nodes from smallest to largest and makes the prefix-sum logic much harder.
• Not updating in-place: Creating a whole new tree instead of modifying the existing one, which uses unnecessary memory.

Interview preparation tip

Always remember: In-order = Ascending, Reverse In-order = Descending for BSTs. If a problem depends on the relative rank of elements in a BST, one of these two traversals is almost certainly the key.