Problem Description

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every node's new value is equal to its original value plus the sum of all node values greater than it in the BST.

• The transformation must be done in-place (modifying the existing tree nodes).
• Each node must include the sum of all nodes with values greater than itself.
• The input is the root node of the BST, and you must return the root of the transformed tree.
• There is always exactly one valid solution for a given BST.
• Do not create new nodes or reuse elements from outside the tree.

Thought Process

To solve this problem, let's recall the properties of a Binary Search Tree (BST): for any node, all nodes in its right subtree have greater values, and all nodes in its left subtree have smaller values.

Our goal is to update each node so it contains its original value plus the sum of all values greater than it. The brute-force way would be, for each node, to traverse the entire tree, summing all greater values. But this would be inefficient, especially for large trees.

Instead, we can exploit the BST property: if we traverse the tree in reverse in-order (right, node, left), we visit nodes from greatest to smallest. This way, we can keep a running sum and update each node as we go, ensuring each node gets the sum of all greater nodes.

Solution Approach

• Reverse In-order Traversal: Traverse the tree in the order: right subtree, current node, left subtree. This visits nodes from largest to smallest.
• Running Sum: Maintain a variable (let's call it sum) to keep track of the sum of all nodes visited so far.
• Update Node Values: For each node, add sum to its value, then update sum to the node's new value.
• Recursive or Iterative: This can be implemented using recursion or an explicit stack for iteration.

By following this approach, each node will hold its original value plus the sum of all greater node values, and the transformation is done in-place.

Example Walkthrough

Consider the BST:

        4
       / \
      1   6
    

• We start at the rightmost node (6). The running sum is 0. Update 6 to 6+0=6. Now, sum=6.
• Move to root (4). Update 4 to 4+6=10. Now, sum=10.
• Move to left node (1). Update 1 to 1+10=11. Now, sum=11.

The transformed tree is:

         10
        /  \
       11   6
      

Time and Space Complexity

• Brute-force:
  • For each node, traverse the whole tree to sum greater values. For n nodes, this is O(n²) time.
  • Space: O(h) for recursion stack (where h is tree height), or O(n) in worst case (skewed tree).
• Optimized Approach (Reverse In-order):
  • Each node is visited exactly once: O(n) time.
  • Space: O(h) due to recursion stack, or O(n) in worst case (skewed tree).

Summary

By leveraging the BST property and using a reverse in-order traversal, we can efficiently convert the tree to a Greater Tree in a single pass. The key insight is to accumulate a running sum as we traverse from largest to smallest, updating each node in-place. This approach is both elegant and optimal, requiring only O(n) time and O(h) space.

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 convertBST(self, root: TreeNode) -> TreeNode:
        self.sum = 0
        def reverse_inorder(node):
            if not node:
                return
            reverse_inorder(node.right)
            self.sum += node.val
            node.val = self.sum
            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 sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        reverseInorder(root);
        return root;
    }
    void reverseInorder(TreeNode* node) {
        if (!node) return;
        reverseInorder(node->right);
        sum += node->val;
        node->val = sum;
        reverseInorder(node->left);
    }
};
      

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

class Solution {
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        reverseInorder(root);
        return root;
    }
    private void reverseInorder(TreeNode node) {
        if (node == null) return;
        reverseInorder(node.right);
        sum += node.val;
        node.val = sum;
        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)
 * }
 */
var convertBST = function(root) {
    let sum = 0;
    function reverseInorder(node) {
        if (!node) return;
        reverseInorder(node.right);
        sum += node.val;
        node.val = sum;
        reverseInorder(node.left);
    }
    reverseInorder(root);
    return root;
};