# Binary Search Tree to Greater Sum Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree)
Canonical: https://scaleengineer.com/dsa/problems/binary-search-tree-to-greater-sum-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [SAP](https://scaleengineer.com/companies/sap), [eBay](https://scaleengineer.com/companies/ebay), [Datadog](https://scaleengineer.com/companies/datadog)
---
## 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/binary-search-tree-to-greater-sum-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 `[1, 100]`.
* `0 <= Node.val <= 100`
* All the values in the tree are **unique**.

**Note:** This question is the same as 538: <https://leetcode.com/problems/convert-bst-to-greater-tree/>

# Approaches
## Brute Force Traversal
This approach iterates through every node in the tree. For each node, it performs another full traversal of the tree to find all nodes with a greater value. The sum of these greater values is then added to the current node's value.
**Time:** O(N^2), where N is the number of nodes. For each of the N nodes, we iterate through N values to find the sum of greater keys. · **Space:** O(N), where N is the number of nodes. This space is used to store the list of all nodes and their original values.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Very inefficient with a time complexity of O(N^2), making it impractical for large trees.; Requires O(N) extra space to store node references and original values.
### Explanation
To avoid issues with modifying node values while they are still needed for comparison, we can first perform a traversal to collect all node references and their original values. Then, for each node, we iterate through the collection of original values to compute the sum of all keys that are greater. This sum is then added to the node's original value. This process is repeated for every node in the tree, resulting in a quadratic time complexity.

```java
/**
 * 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 bstToGst(TreeNode root) {
        // Store all nodes to iterate through them
        List<TreeNode> allNodes = new ArrayList<>();
        collectNodes(root, allNodes);

        // Store all original values for comparison
        List<Integer> originalValues = new ArrayList<>();
        for (TreeNode node : allNodes) {
            originalValues.add(node.val);
        }

        // For each node, calculate the sum of greater values and update it
        for (TreeNode node : allNodes) {
            int sumOfGreater = 0;
            for (int val : originalValues) {
                if (val > node.val) {
                    sumOfGreater += val;
                }
            }
            node.val += sumOfGreater;
        }
        return root;
    }

    private void collectNodes(TreeNode node, List<TreeNode> allNodes) {
        if (node == null) {
            return;
        }
        allNodes.add(node);
        collectNodes(node.left, allNodes);
        collectNodes(node.right, allNodes);
    }
}
```
### Algorithm
*   Traverse the tree (e.g., using in-order traversal) and store all node references in a list, say `allNodes`.
*   Create a copy of the original values from `allNodes` into an array, `originalValues`.
*   Iterate through each `node` in the `allNodes` list.
*   For each `node`, initialize a `sumOfGreater` to 0.
*   Iterate through the `originalValues` array. If a value `v` is greater than the current `node`'s original value, add `v` to `sumOfGreater`.
*   Update the node's value: `node.val = node.val + sumOfGreater`.
*   After iterating through all nodes, the tree is transformed. Return the root.

## Two-Pass with In-order Traversal and Suffix Sums
A more optimized approach involves recognizing that an in-order traversal of a BST visits nodes in ascending order. We can leverage this property to calculate the new values more efficiently in two passes.
**Time:** O(N). The in-order traversal takes O(N), calculating suffix sums and building the map takes O(N), and the final update traversal takes O(N). · **Space:** O(N). 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, where H is the tree height (O(N) in the worst case).
**Pros:** Significantly more efficient than the brute-force approach with a linear time complexity.; The logic is straightforward, separating the calculation from the tree modification.
**Cons:** Requires multiple passes over the data (one to collect values, one to update the tree).; Uses O(N) extra space for the list and map, which can be suboptimal compared to a single-pass approach.
### Explanation
The process involves three main steps. First, we perform an in-order traversal to collect all node values into a list, which will naturally be sorted. Second, we compute the suffix sums for this sorted list. The suffix sum at any position `i` is the sum of all elements from `i` to the end, which corresponds exactly to the new value for the node with `sortedValues[i]`. We can store these old-value-to-new-value mappings in a hash map. Finally, we traverse the tree a second time, and for each node, we update its value using the mapping created in the previous step.

```java
/**
 * 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 bstToGst(TreeNode root) {
        // 1. Get sorted values via in-order traversal
        List<Integer> sortedValues = new ArrayList<>();
        inorder(root, sortedValues);

        // 2. Create a map of original value to new value using suffix sums
        Map<Integer, Integer> valueMap = new HashMap<>();
        int n = sortedValues.size();
        int suffixSum = 0;
        for (int i = n - 1; i >= 0; i--) {
            suffixSum += sortedValues.get(i);
            valueMap.put(sortedValues.get(i), suffixSum);
        }

        // 3. Traverse the tree again to update values
        updateTree(root, valueMap);
        return root;
    }

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

    private void updateTree(TreeNode node, Map<Integer, Integer> valueMap) {
        if (node == null) return;
        node.val = valueMap.get(node.val);
        updateTree(node.left, valueMap);
        updateTree(node.right, valueMap);
    }
}
```
### Algorithm
*   Perform an in-order traversal of the BST and store the node values in a list, `sortedValues`. This list will be sorted in ascending order.
*   Create a hash map, `valueMap`, to store the mapping from an original value to its new greater-sum value.
*   Iterate through `sortedValues` from right to left (from largest to smallest value).
*   Maintain a running `suffixSum`. In each step, add the current value to `suffixSum` and put the mapping (`originalValue`, `suffixSum`) into `valueMap`.
*   Perform a second traversal of the tree (e.g., pre-order).
*   For each node, update its value using the map: `node.val = valueMap.get(node.val)`.
*   Return the root of the modified tree.

## Optimal Single-Pass Reverse In-order Traversal
The most efficient solution involves a single traversal of the tree. Since we need to sum up all values *greater* than the current node's value, it's natural to process nodes in descending order. A standard in-order traversal (Left-Root-Right) visits nodes in ascending order. By reversing this to a Right-Root-Left traversal, we can visit nodes in descending order and accumulate the sum in one pass.
**Time:** O(N), as we visit each node exactly once. · **Space:** O(H), where H is the height of the tree, for the recursion stack. In a balanced tree, this is O(log N). In the worst case of a skewed tree, it becomes O(N).
**Pros:** Optimal time complexity (O(N)) with a single pass.; Elegant and concise recursive implementation.; Space complexity is better than the two-pass approach on average (O(log N) vs O(N)).
**Cons:** The recursive solution can lead to a stack overflow for extremely deep trees, though this is not an issue with the given constraints. An iterative version using a stack can mitigate this.
### Explanation
We can perform a reverse in-order traversal, keeping track of a running sum of the values of the nodes visited so far. Since we visit nodes from largest to smallest, this running sum at any point represents the sum of all keys greater than the current node's key. The algorithm can be implemented recursively. We maintain a sum variable (as a class member or passed by reference), initialized to 0. The traversal function first recursively calls itself on the right child. After returning from the right subtree, it processes the current node by adding its value to the running sum and updating the node's value to this new sum. Finally, it recursively calls itself on the left child. This ensures that by the time we process a node, the sum already contains the total of all larger keys.

```java
/**
 * 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 {
    private int sum = 0;

    public TreeNode bstToGst(TreeNode root) {
        if (root != null) {
            // 1. Traverse the right subtree first (all values are greater)
            bstToGst(root.right);
            
            // 2. Process the current node
            sum += root.val; // Add current value to sum
            root.val = sum;  // Update current node's value
            
            // 3. Traverse the left subtree (all values are smaller)
            bstToGst(root.left);
        }
        return root;
    }
}
```
### Algorithm
*   Initialize a `sum` variable to 0. This variable will accumulate the sum of keys as we traverse.
*   Define a traversal function that takes a `node` as input.
*   Base case: If the `node` is null, return.
*   Recursively call the traversal function on the `node.right` child. This processes all nodes with greater values first.
*   Process the current `node`:
    *   Add the node's original value to the `sum`.
    *   Update the node's value to the new `sum`.
*   Recursively call the traversal function on the `node.left` child. This processes all nodes with smaller values.
*   Start the process by calling the traversal function with the `root`.

# Solutions
### Java

```java
/** * 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 bstToGst ( 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 ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {TreeNode} */ var bstToGst =
  function (root) {
    let s = 0;
    function dfs(root) {
      if (!root) {
        return;
      }
      dfs(root.right);
      s += root.val;
      root.val = s;
      dfs(root.left);
    }
    dfs(root);
    return root;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * bstToGst ( TreeNode * root ) { int s = 0 ; TreeNode * node = root ; while ( root ) { if ( root -> right == nullptr ) { s += root -> val ; root -> val = s ; root = root -> left ; } else { TreeNode * next = root -> right ; while ( next -> left && next -> left != root ) { next = next -> left ; } if ( next -> left == nullptr ) { next -> left = root ; root = root -> right ; } else { s += root -> val ; root -> val = s ; next -> left = nullptr ; 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 class Solution : def bstToGst ( self , root : TreeNode ) -> TreeNode : s = 0 node = root while root : if root . right is None : s += root . val root . val = s root = root . left else : next = root . right while next . left and next . left != root : next = next . left if next . left is None : next . left = root root = root . right else : s += root . val root . val = s next . left = None root = root . left return node
```