538. Convert BST to Greater Tree

Intuition

The goal is to transform the given Binary Search Tree (BST) such that each node's value is updated to be the original node value plus the sum of all node values greater than the original node value. To achieve this, we can leverage the properties of the BST and perform a reverse in-order traversal (right-root-left). During this traversal, we maintain a running sum of all visited nodes, which allows us to update each node's value correctly.

Approach

1. Reverse In-order Traversal: The key idea is to traverse the BST in a reverse in-order manner. This means we process the right subtree first, then the current node, and finally the left subtree. This traversal ensures that we visit nodes in descending order.
2. Running Sum: Maintain a running sum of all node values visited so far. Initialize this sum to 0.
3. Update Node Values: As we visit each node during the traversal, add the node's value to the running sum and update the node's value with the running sum.
4. Recursive Helper Function: Define a helper function dfs to perform the reverse in-order traversal and update the node values.

Steps:

1. Start from the root of the BST.
2. Traverse the right subtree recursively.
3. Update the running sum and the current node's value.
4. Traverse the left subtree recursively.

Complexity

Time Complexity

The time complexity of the convertBST function is \( O(n) \), where \( n \) is the number of nodes in the Binary Search Tree (BST). This is because the function performs a reverse in-order traversal of the BST, visiting each node exactly once.

Space Complexity

The space complexity of the convertBST function is \( O(h) \), where \( h \) is the height of the BST. This space is primarily used by the recursion stack during the traversal. In the worst case, for a skewed BST where the height \( h \) is \( O(n) \), the space complexity would be \( O(n) \). However, for a balanced BST, the height \( h \) is \( O(log n) \), resulting in a space complexity of \( O(log n) \).

Code

C++

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        
        function dfs = [&](TreeNode* node) {
            if (!node) return;
            dfs(node->right);
            sum += node->val;
            node->val = sum;
            dfs(node->left);
        };
        
        dfs(root);
        return root;
    }
};

Python

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        self.sum = 0
        
        def dfs(node):
            if not node:
                return
            if node.right:
                dfs(node.right)
            self.sum += node.val
            node.val = self.sum
            if node.left:
                dfs(node.left)
        
        dfs(root)
        return root

Java

class Solution {
    private int sum = 0;
    
    public TreeNode convertBST(TreeNode root) {
        dfs(root);        
        return root;
    }
    
    private void dfs(TreeNode node) {
        if (node == null) return;        
        dfs(node.right);
        sum += node.val;
        node.val = sum;
        dfs(node.left);
    }
}

JavaScript

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function (root) {
    var sum = 0;

    var dfs = function (node) {
        if (!node) return;
        dfs(node.right);
        sum += node.val;
        node.val = sum;
        dfs(node.left);
    };

    dfs(root);
    return root;
};