Convert BST to Greater Tree

Problem

Convert a BST so each node value equals the sum of all original values >= node's original value.

Key insight: Reverse in-order (right → node → left) gives decreasing order. Accumulate running sum.

Solutions

// C
int runningSum = 0;
TreeNode* convertBST(TreeNode* root) {
    if (!root) return NULL;
    convertBST(root->right);
    runningSum += root->val;
    root->val = runningSum;
    convertBST(root->left);
    return root;
}

// C++
int runningSum = 0;
TreeNode* convertBST(TreeNode* root) {
    if (!root) return nullptr;
    convertBST(root->right);
    runningSum += root->val;
    root->val = runningSum;
    convertBST(root->left);
    return root;
}

// Java
int runningSum = 0;
public TreeNode convertBST(TreeNode root) {
    if (root == null) return null;
    convertBST(root.right);
    runningSum += root.val;
    root.val = runningSum;
    convertBST(root.left);
    return root;
}

// JavaScript
function convertBST(root) {
    let sum = 0;
    function dfs(node) {
        if (!node) return;
        dfs(node.right);
        sum += node.val;
        node.val = sum;
        dfs(node.left);
    }
    dfs(root);
    return root;
}

# Python
def convertBST(root):
    running = [0]
    def dfs(node):
        if not node:
            return
        dfs(node.right)
        running[0] += node.val
        node.val = running[0]
        dfs(node.left)
    dfs(root)
    return root

Complexity

Time: O(n)
Space: O(h)

Key Insight

Reverse in-order = right, root, left. In a BST, this visits nodes in decreasing order — perfect for a suffix sum.