# Convert BST to Greater Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/convert-bst-to-greater-tree)
Canonical: https://scaleengineer.com/dsa/problems/convert-bst-to-greater-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## Problem
Given the `root` of a Binary Search Tree (BST), 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 BST.

As a reminder, a _binary search tree_ is a tree that satisfies these constraints:

* The left subtree of a node contains only nodes with keys **less than** the node's key.
* The right subtree of a node contains only nodes with keys **greater than** the node's key.
* Both the left and right subtrees must also be binary search trees.

**Example 1:**

![](https://assets.glich.co/dsa/convert-bst-to-greater-tree/image0.png) 

**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]

**Example 2:**

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

**Constraints:**

* The number of nodes in the tree is in the range `[0, 104]`.
* `-104 <= Node.val <= 104`
* All the values in the tree are **unique**.
* `root` is guaranteed to be a valid binary search tree.

**Note:** This question is the same as 1038: <https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/>

# Approaches
## Brute Force with Nested Traversal
This approach iterates through each node of the tree. For each node, it performs a separate, full traversal of the tree to find and sum all the keys that are greater than the current node's key. The current node's value is then updated with the sum of its original value and this calculated sum.
**Time:** O(N^2), where N is the number of nodes. The initial traversal to collect values is O(N). The second traversal to update nodes involves, for each of the N nodes, an iteration over the N collected values, leading to O(N*N) work. · **Space:** O(N), where N is the number of nodes. This space is used to store the list of all values from the tree. The recursion stack for traversal also contributes up to O(H) space, where H is the tree height.
**Pros:** Simple to understand as it directly follows the problem's definition.
**Cons:** Extremely inefficient with a time complexity of O(N^2).; Requires O(N) extra space to store node values and/or references.; Complex to implement correctly without running into issues of modifying the tree while reading from it.
### Explanation
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.

```java
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        // 1. Collect all original values from the tree.
        List<Integer> allValues = new ArrayList<>();
        collectAllValues(root, allValues);

        // 2. Traverse the tree again to update each node.
        updateNodeValues(root, allValues);
        
        return root;
    }

    private void collectAllValues(TreeNode node, List<Integer> allValues) {
        if (node == null) return;
        allValues.add(node.val);
        collectAllValues(node.left, allValues);
        collectAllValues(node.right, allValues);
    }

    private void updateNodeValues(TreeNode node, List<Integer> allValues) {
        if (node == null) return;

        // For the current node, find the sum of all greater values.
        int sumOfGreater = 0;
        for (int val : allValues) {
            if (val > node.val) {
                sumOfGreater += val;
            }
        }
        // Update the node's value.
        node.val += sumOfGreater;

        // Recursively update the rest of the tree.
        updateNodeValues(node.left, allValues);
        updateNodeValues(node.right, allValues);
    }
}
```
### Algorithm
- 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.

## Two-Pass using In-order Traversal
This approach leverages the property of a BST that an in-order traversal visits nodes in ascending order of their keys. We can first get a sorted list of all node values, then calculate the new value for each key, and finally traverse the tree again to update the nodes.
**Time:** O(N). The in-order traversal takes O(N), calculating suffix sums and populating the map takes O(N), and the final update traversal takes O(N). The total is O(N + N + N) = O(N). · **Space:** O(N), where N is the number of nodes. We need O(N) space for the `sortedValues` list and O(N) for the `valueMap`. The recursion stack for traversals also takes up to O(H) space.
**Pros:** Efficient time complexity of O(N).; Conceptually clear, separating the calculation logic from the tree update logic.
**Cons:** Requires O(N) auxiliary space for the list of values and the map.; Requires two separate passes over the tree.
### Explanation
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.

```java
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;

        // 1. Get sorted values using in-order traversal
        List<Integer> sortedValues = new ArrayList<>();
        inorderTraversal(root, sortedValues);

        // 2. Calculate suffix sums and map old values to new values
        Map<Integer, Integer> valueMap = new HashMap<>();
        int sum = 0;
        for (int i = sortedValues.size() - 1; i >= 0; i--) {
            int val = sortedValues.get(i);
            sum += val;
            valueMap.put(val, sum);
        }

        // 3. Traverse the tree again to update node values
        updateNodes(root, valueMap);

        return root;
    }

    private void inorderTraversal(TreeNode node, List<Integer> values) {
        if (node == null) return;
        inorderTraversal(node.left, values);
        values.add(node.val);
        inorderTraversal(node.right, values);
    }

    private void updateNodes(TreeNode node, Map<Integer, Integer> valueMap) {
        if (node == null) return;
        // The original value of the node is used as the key
        node.val = valueMap.get(node.val);
        updateNodes(node.left, valueMap);
        updateNodes(node.right, valueMap);
    }
}
```
### Algorithm
- 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)`.

## Optimal Single-Pass with Reverse In-order Traversal
The most efficient approach involves a single traversal of the tree. Since we need to sum up all keys greater than the current key, it's beneficial to process the keys in descending order. A standard in-order traversal (Left-Root-Right) visits nodes in ascending order. By modifying this to a reverse in-order traversal (Right-Root-Left), we can visit nodes in descending order and update them in a single pass.
**Time:** O(N), as each node is visited exactly once during the single traversal. · **Space:** O(H), where H is the height of the tree. This space is consumed by the recursion call stack or the explicit stack in the iterative version. For a balanced BST, this is O(log N). In the worst case of a skewed tree, it is O(N).
**Pros:** Optimal O(N) time complexity with a single pass.; Space-efficient, using O(H) space which is O(log N) for a balanced tree.; Elegant and concise solution, modifying the tree in-place.
**Cons:** The recursive solution can cause a stack overflow for extremely deep and skewed trees.; The logic of reverse in-order traversal might be slightly less intuitive at first than a standard traversal.
### Explanation
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:**
```java
class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            // 1. Traverse the right subtree first (larger values)
            convertBST(root.right);
            
            // 2. Process the current node
            sum += root.val;
            root.val = sum;
            
            // 3. Traverse the left subtree (smaller values)
            convertBST(root.left);
        }
        return root;
    }
}
```

**Iterative Implementation (using a Stack):**
```java
class Solution {
    public TreeNode convertBST(TreeNode root) {
        int sum = 0;
        TreeNode current = root;
        Stack<TreeNode> stack = new Stack<>();

        while (current != null || !stack.isEmpty()) {
            // Go to the rightmost node of the current subtree
            while (current != null) {
                stack.push(current);
                current = current.right;
            }

            // Process the node at the top of the stack
            current = stack.pop();
            sum += current.val;
            current.val = sum;

            // Move to the left subtree to process smaller values
            current = current.left;
        }
        return root;
    }
}
```
### Algorithm
- 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.

# Solutions
### Java

```java
public class Convert_BST_to_Greater_Tree { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int sum = 0 ; public TreeNode convertBST ( TreeNode root ) { if ( root == null ) { return null ; } convertBST ( root . right ); sum += root . val ; root . val = sum ; convertBST ( root . left ); return root ; } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode convertBST ( TreeNode root ) { int s = 0 ; TreeNode node = root ; while ( root != null ) { if ( root . right == null ) { s += root . val ; root . val = s ; root = root . left ; } else { TreeNode next = root . right ; while ( next . left != null && next . left != root ) { next = next . left ; } if ( next . left == null ) { next . left = root ; root = root . right ; } else { s += root . val ; root . val = s ; next . left = null ; root = root . left ; } } } return node ; } }
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right # same but just left/right mirror of https://leetcode.ca/2016-03-03-94-Binary-Tree-Inorder-Traversal/ class Solution : def convertBST ( self , root : Optional [ TreeNode ]) -> Optional [ TreeNode ]: stack = [] current = root s = 0 # sum while stack or current : while current : stack . append ( current ) current = current . right right_or_middle = stack . pop () s += right_or_middle . val right_or_middle . val = s current = right_or_middle . left return root ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def __init__ ( self ): self . lSum = 0 def convertBST ( self , root ): """ :type root: TreeNode :rtype: TreeNode """ if not root : return None self . convertBST ( root . right ) self . lSum += root . val root . val = self . lSum self . convertBST ( root . left ) return root
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/convert-bst-to-greater-tree/ // Time: O(N) // Space: O(H) class Solution { int sum = 0 ; public: TreeNode * convertBST ( TreeNode * root ) { if ( ! root ) return nullptr ; convertBST ( root -> right ); root -> val = ( sum += root -> val ); convertBST ( root -> left ); return root ; } };
```