Problem Description

Given the root of a binary search tree (BST), you are asked to transform the tree into a Greater Sum Tree (GST). In the resulting tree, every node's value is replaced by the sum of all values greater than or equal to that node's value in the original BST.

Formally, for each node with value val in the BST, its new value should be the sum of all node values in the BST that are greater than or equal to val.

Constraints:

• The input is a valid BST (all left descendants are less, all right descendants are greater).
• All node values are unique integers.
• You must modify the tree in-place and return its root.

Thought Process

To solve this problem, let's first consider what it means to replace each node with the sum of all greater or equal values. In a BST, an in-order traversal (left-root-right) gives us nodes in ascending order, but we want to accumulate from the largest to the smallest. This suggests we should traverse the tree in reverse in-order (right-root-left).

A brute-force approach might be, for each node, to search the entire tree and sum all values greater or equal to it. However, this would be very inefficient, especially for large trees.

Instead, we can use the BST properties to visit nodes in descending order and keep a running sum as we go, updating each node's value in-place. This avoids redundant work and leverages the sorted nature of the BST.

Solution Approach

Here's how we can efficiently transform the BST to a Greater Sum Tree:

1. Reverse In-order Traversal: Traverse the tree in the order: right subtree, current node, left subtree. This visits nodes from largest to smallest.
2. Running Sum: Maintain a variable (e.g., total) to keep track of the sum of all nodes visited so far.
3. Update Node Values: For each node visited, add its original value to total, then set the node's value to total.
4. Recursive or Iterative: This can be implemented recursively (simpler, more readable) or iteratively using a stack.

This approach leverages the BST's ordering, so each node is visited only once, and the running sum ensures we always know the sum of all greater or equal values.

Example Walkthrough

Let's walk through an example with a simple BST:

        4
       / \
      1   6
         / \
        5   7
  

• Start with total = 0.
• Reverse in-order traversal visits: 7, 6, 5, 4, 1.
• Visit 7: total += 7 → total = 7. Set 7's value to 7.
• Visit 6: total += 6 → total = 13. Set 6's value to 13.
• Visit 5: total += 5 → total = 18. Set 5's value to 18.
• Visit 4: total += 4 → total = 22. Set 4's value to 22.
• Visit 1: total += 1 → total = 23. Set 1's value to 23.

The final GST is:

        22
       /  \
     23   13
          / \
        18   7
  

Time and Space Complexity

• Brute-force approach: For each node, sum all greater or equal nodes (O(N) per node), leading to O(N²) time.
• Optimized approach: Each node is visited exactly once in the reverse in-order traversal. Thus, the time complexity is O(N), where N is the number of nodes.
• Space complexity: O(H), where H is the height of the tree, due to the recursion stack (or stack in an iterative approach). In the worst case (skewed tree), H = N; in the best case (balanced), H = log N.

Summary

By leveraging the properties of a binary search tree and using a reverse in-order traversal, we can efficiently compute the Greater Sum Tree in a single pass. The key insight is to accumulate a running sum as we visit nodes from largest to smallest, updating each node in-place. This avoids redundant computation and makes the solution both elegant and efficient.

Code Implementation

# 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:
        self.total = 0

        def reverse_inorder(node):
            if not node:
                return
            reverse_inorder(node.right)
            self.total += node.val
            node.val = self.total
            reverse_inorder(node.left)

        reverse_inorder(root)
        return root
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int total = 0;
    TreeNode* bstToGst(TreeNode* root) {
        reverseInorder(root);
        return root;
    }
    void reverseInorder(TreeNode* node) {
        if (!node) return;
        reverseInorder(node->right);
        total += node->val;
        node->val = total;
        reverseInorder(node->left);
    }
};
      

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private int total = 0;
    public TreeNode bstToGst(TreeNode root) {
        reverseInorder(root);
        return root;
    }

    private void reverseInorder(TreeNode node) {
        if (node == null) return;
        reverseInorder(node.right);
        total += node.val;
        node.val = total;
        reverseInorder(node.left);
    }
}
      

/**
 * 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 total = 0;
    function reverseInorder(node) {
        if (!node) return;
        reverseInorder(node.right);
        total += node.val;
        node.val = total;
        reverseInorder(node.left);
    }
    reverseInorder(root);
    return root;
};