Convert BST to Greater Tree

medium tree bst dfs

Problem

Convert a BST into a Greater Tree where every node's new value equals the sum of all original keys ≥ that node's key.

Inputtree = [4, 1, 6, 0, 2, 5, 7]

Output[22, 25, 13, 25, 24, 18, 7]

Sum of keys ≥ x for each x → e.g. for key 4: 4 + 5 + 6 + 7 = 22 (the node itself plus everything greater).

tree (BST level-order, "null" for empty)

def convert_bst(root):
    s = 0

    def dfs(n):
        nonlocal s
        if not n:
            return
        dfs(n.right)
        s += n.val
        n.val = s
        dfs(n.left)

    dfs(root)
    return root

function convertBST(root) {
  let s = 0;
  function dfs(n) {
    if (!n) return;
    dfs(n.right);
    s += n.val;
    n.val = s;
    dfs(n.left);
  }
  dfs(root);
  return root;
}

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

TreeNode* convertBST(TreeNode* root) {
    int s = 0;
    function<void(TreeNode*)> dfs = [&](TreeNode* n) {
        if (!n) return;
        dfs(n->right);
        s += n->val;
        n->val = s;
        dfs(n->left);
    };
    dfs(root);
    return root;
}

Explanation

Each node's new value should be its own key plus the sum of all keys greater than it. The clever trick is a reverse in-order traversal: visit right, then the node, then left, which walks the BST from largest to smallest.

We carry a running total s. Because we see values in decreasing order, by the time we reach a node we have already added every key bigger than it. So we do s += n.val and then overwrite n.val = s.

Visiting the right subtree first is what makes this work — all larger keys are processed before the current node, so s always holds exactly the sum of keys ≥ the current one.

Example: BST [4, 1, 6, 0, 2, 5, 7]. Reverse order is 7, 6, 5, 4, 2, 1, 0. Node 7 becomes 7, node 6 becomes 13, node 5 becomes 18, node 4 becomes 22, and so on down the line.

One pass updates every node, since the running sum quietly accumulates all the "greater" keys as we go.

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