Binary Search Tree to Greater Sum Tree - Video Solutions

Problem Overview: You are given a binary search tree where each node must be updated so its new value equals the original value plus the sum of all keys greater than it. The structure of the tree stays the same; only node values change.

Approach 1: Reverse In-Order Traversal (DFS) (Time: O(n), Space: O(h))

A BST visited in reverse in-order order (right → node → left) processes nodes from largest to smallest. Maintain a running variable sum that stores the cumulative total of nodes already visited. When you reach a node, add its value to sum and update the node with this new total. Because nodes are visited in descending order, sum always represents the sum of all greater values. This approach relies on depth-first search and the ordering property of a BST. The recursion depth equals the tree height h, giving O(h) auxiliary space. For balanced trees this is O(log n), while a skewed tree degrades to O(n).

The key insight is exploiting the BST ordering. Instead of computing greater sums by scanning other nodes, you accumulate them naturally while traversing from the largest value downward. This produces an optimal linear-time solution and minimal extra state.

Approach 2: Iterative Traversal Using a Stack (Time: O(n), Space: O(h))

The same reverse in-order logic can be implemented iteratively with an explicit stack. Start from the root and push nodes while moving right to reach the maximum element. Pop a node, update the running sum, modify the node value, then move to its left subtree. Repeat the process until the stack becomes empty. Each node is pushed and popped once, keeping the time complexity O(n).

This approach avoids recursion and is useful in environments where stack depth is a concern. The stack stores at most the height of the tree, so space complexity remains O(h). The algorithm still leverages the sorted property of a binary tree structured as a BST, ensuring nodes are processed in descending order.

Recommended for interviews: Reverse in-order traversal is the expected solution. It demonstrates understanding of BST ordering and how DFS traversal patterns can transform data efficiently. Mentioning the iterative stack variant shows awareness of recursion limits and gives a practical alternative while keeping the same O(n) performance.