Convert BST to Greater Tree

• Create a helper function collectValues that performs a tree traversal (e.g., pre-order) to store all original node values in a list.
• Create another helper function updateNodes that also traverses the tree.
• In updateNodes, for each node:
  • Store its original value, originalVal = node.val.
  • Initialize a sumOfGreater = 0.
  • Iterate through the list of all collected values. If a value v is greater than originalVal, add v to sumOfGreater.
  • Update the node's value: node.val = originalVal + sumOfGreater.
• This approach is flawed if we modify the tree in place. A correct but slow implementation would be:
  1. Traverse the tree to get a list of all nodes and a list of all original values.
  2. For each node in the node list, calculate its new value by iterating through the value list.
  3. Store these new values in a map from node to new value.
  4. Finally, iterate through the map and update the tree.

The brute-force method directly translates the problem statement into a naive algorithm. The core idea is that for every single node in the tree, we need to find the sum of all nodes with a greater value. The most straightforward way to do this is to perform a full tree scan for each node.

To avoid issues with modifying the tree's values while they are still needed for comparison, we must first cache all the original values. The algorithm proceeds by first traversing the entire tree to collect all node values into an auxiliary list. Then, for each node in the tree (requiring another traversal), we iterate through our cached list of values to compute the sum of all greater elements. Finally, we update the node's value. This results in a nested loop structure, where the outer loop is over the nodes and the inner loop is over the values, leading to quadratic time complexity.

1class Solution {2    public TreeNode convertBST(TreeNode root) {3        if (root == null) return null;4        // 1. Collect all original values from the tree.5        List<Integer> allValues = new ArrayList<>();6        collectAllValues(root, allValues);7 8        // 2. Traverse the tree again to update each node.9        updateNodeValues(root, allValues);10        11        return root;12    }13 14    private void collectAllValues(TreeNode node, List<Integer> allValues) {15        if (node == null) return;16        allValues.add(node.val);17        collectAllValues(node.left, allValues);18        collectAllValues(node.right, allValues);19    }20 21    private void updateNodeValues(TreeNode node, List<Integer> allValues) {22        if (node == null) return;23 24        // For the current node, find the sum of all greater values.25        int sumOfGreater = 0;26        for (int val : allValues) {27            if (val > node.val) {28                sumOfGreater += val;29            }30        }31        // Update the node's value.32        node.val += sumOfGreater;33 34        // Recursively update the rest of the tree.35        updateNodeValues(node.left, allValues);36        updateNodeValues(node.right, allValues);37    }38}

• Perform an in-order traversal of the BST. This visits the nodes in ascending order of their keys. Store these keys in a list, sortedValues.
• Create a map, valueToGreaterSum, to store the mapping from an original key to its new value in the Greater Tree.
• Iterate through the sortedValues list from right to left (i.e., from largest to smallest key).
• Maintain a running sum. For each value v in the list, add v to sum and then store the mapping: valueToGreaterSum.put(v, sum).
• Perform a second traversal of the tree (in any order, e.g., pre-order).
• In this second traversal, for each node, update its value using the map: node.val = valueToGreaterSum.get(node.val).

A significant improvement over the brute-force method comes from utilizing the inherent order of a BST. An in-order traversal (Left-Root-Right) of a BST yields the node values in a sorted (non-decreasing) sequence.

The algorithm works in two main phases:

1. Data Collection and Processing: We perform an in-order traversal to get a sorted list of all node values. With this sorted list, we can efficiently calculate the new value for each key. The new value for any key k is the sum of all keys greater than or equal to k. This is equivalent to a suffix sum on the sorted list. We can compute these suffix sums in a single pass over the sorted list (from right to left) and store the results in a hash map, mapping each original value to its new Greater Tree value.
2. Tree Update: We perform a second traversal of the tree. For each node, we look up its original value in our hash map and update the node's value to the new, pre-calculated Greater Tree value.

1class Solution {2    public TreeNode convertBST(TreeNode root) {3        if (root == null) return null;4 5        // 1. Get sorted values using in-order traversal6        List<Integer> sortedValues = new ArrayList<>();7        inorderTraversal(root, sortedValues);8 9        // 2. Calculate suffix sums and map old values to new values10        Map<Integer, Integer> valueMap = new HashMap<>();11        int sum = 0;12        for (int i = sortedValues.size() - 1; i >= 0; i--) {13            int val = sortedValues.get(i);14            sum += val;15            valueMap.put(val, sum);16        }17 18        // 3. Traverse the tree again to update node values19        updateNodes(root, valueMap);20 21        return root;22    }23 24    private void inorderTraversal(TreeNode node, List<Integer> values) {25        if (node == null) return;26        inorderTraversal(node.left, values);27        values.add(node.val);28        inorderTraversal(node.right, values);29    }30 31    private void updateNodes(TreeNode node, Map<Integer, Integer> valueMap) {32        if (node == null) return;33        // The original value of the node is used as the key34        node.val = valueMap.get(node.val);35        updateNodes(node.left, valueMap);36        updateNodes(node.right, valueMap);37    }38}

• The core idea is to traverse the tree's nodes in descending order.
• This can be achieved with a reverse in-order traversal (Right, Root, Left).
• Maintain a running sum, initialized to 0, that accumulates the values of the nodes as they are visited.
• Recursive Implementation:
  1. Define a recursive function that takes a node as input.
  2. The base case is if the node is null, simply return.
  3. First, make a recursive call on the node.right child.
  4. After the right subtree has been fully processed, visit the current node. Add its value to the running sum (sum += node.val) and then update the node's value with this new sum (node.val = sum).
  5. Finally, make a recursive call on the node.left child.
• Iterative Implementation:
  1. Use a Stack to mimic the recursion.
  2. Push nodes onto the stack while traversing as far right as possible.
  3. Pop a node, process it (update sum and node value), and then move to its left child.

This optimal solution cleverly uses a single pass. The key insight is that to update a node's value, we need the sum of all values greater than it. If we could visit the nodes in descending order (from largest to smallest), we could maintain a running sum and update each node as we visit it.

In a BST, a reverse in-order traversal (Right, Root, Left) accomplishes exactly this. The algorithm maintains a single sum variable, initialized to 0. As it traverses the tree:

1. It first goes to the rightmost node (the largest value).
2. It processes this node, adding its value to sum and updating the node's value to sum.
3. It then moves to the next largest node (the in-order predecessor), adds its value to the now-updated sum, and updates its own value.

This process continues, ensuring that when any node is visited, the sum variable already holds the sum of all nodes with greater values. This method is highly efficient as it modifies the tree in place with just one traversal.

Recursive Implementation:

1class Solution {2    private int sum = 0;3 4    public TreeNode convertBST(TreeNode root) {5        if (root != null) {6            // 1. Traverse the right subtree first (larger values)7            convertBST(root.right);8            9            // 2. Process the current node10            sum += root.val;11            root.val = sum;12            13            // 3. Traverse the left subtree (smaller values)14            convertBST(root.left);15        }16        return root;17    }18}

Iterative Implementation (using a Stack):

1class Solution {2    public TreeNode convertBST(TreeNode root) {3        int sum = 0;4        TreeNode current = root;5        Stack<TreeNode> stack = new Stack<>();6 7        while (current != null || !stack.isEmpty()) {8            // Go to the rightmost node of the current subtree9            while (current != null) {10                stack.push(current);11                current = current.right;12            }13 14            // Process the node at the top of the stack15            current = stack.pop();16            sum += current.val;17            current.val = sum;18 19            // Move to the left subtree to process smaller values20            current = current.left;21        }22        return root;23    }24}