Convert BST to Greater Tree

Convert BST to Greater Tree

What is this problem about?

The Convert BST to Greater Tree interview question asks you to modify a BST such that every node's value is replaced by its original value plus the sum of all values strictly greater than it in the original BST.

Why is this asked in interviews?

This Convert BST to Greater Tree coding problem is common at Microsoft and Amazon. It tests whether a candidate can modify standard traversal algorithms to fit specific constraints. It specifically checks if you realize that a "Reverse In-order Traversal" (Right, Root, Left) visits nodes in descending order, making it easy to maintain a running sum.

Algorithmic pattern used

This follows the Binary Search Tree, Depth-First Search interview pattern.

• Standard In-order: Left -> Root -> Right (Ascending).
• Reverse In-order: Right -> Root -> Left (Descending).
• Maintain a global or passed-by-reference running_sum.
• At each node:
  1. Visit Right child.
  2. running_sum += node.val.
  3. node.val = running_sum.
  4. Visit Left child.

Example explanation

BST:

    4
   / 
  1   6

1. Visit Right: 6. running_sum = 6, node.val = 6.
2. Visit Root: 4. running_sum = 6 + 4 = 10, node.val = 10.
3. Visit Left: 1. running_sum = 10 + 1 = 11, node.val = 11. Result Tree:

    10
   /  
  11   6

Common mistakes candidates make

• Redundant sums: Calculating the sum of larger nodes for each node individually (O(N^2)) instead of using a running sum (O(N)).
• Wrong traversal: Using a standard in-order traversal and then trying to adjust values backward.
• Scope errors: Not correctly updating the running_sum variable across recursive boundaries.

Interview preparation tip

Whenever a BST problem involves "greater than" or "smaller than" relationships, think about which direction of in-order traversal (ascending or descending) will let you process the data in the right order.