Binary Search Tree to Greater Sum Tree

medium binary search tree reverse inorder dfs

Problem

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is replaced with the original key plus the sum of all keys greater than the original key. Because it is a BST, a reverse in-order traversal (right, node, left) visits keys from largest to smallest, so a single running total lets us update each node in place.

Inputnums = [2, 1, 3] (level order, builds BST root 2)

Output[5, 6, 3]

Largest key 3 stays 3; key 2 becomes 2 + 3 = 5; key 1 becomes 1 + 5 = 6.

BST keys (comma-separated, distinct)

def bstToGst(root):
    acc = 0
    def dfs(node):
        nonlocal acc
        if not node:
            return
        dfs(node.right)
        acc += node.val
        node.val = acc
        dfs(node.left)
    dfs(root)
    return root

function bstToGst(root) {
  let acc = 0;
  function dfs(node) {
    if (!node) return;
    dfs(node.right);
    acc += node.val;
    node.val = acc;
    dfs(node.left);
  }
  dfs(root);
  return root;
}

class Solution {
    private int acc = 0;
    public TreeNode bstToGst(TreeNode node) {
        if (node == null) return node;
        bstToGst(node.right);
        acc += node.val;
        node.val = acc;
        bstToGst(node.left);
        return node;
    }
}

class Solution {
    int acc = 0;
public:
    TreeNode* bstToGst(TreeNode* node) {
        if (node == nullptr) return node;
        bstToGst(node->right);
        acc += node->val;
        node->val = acc;
        bstToGst(node->left);
        return node;
    }
};

Explanation

Each node should become its own value plus the sum of every larger key. The slick idea is to visit the keys from largest to smallest while carrying a running total.

A normal in-order walk (left, node, right) visits a BST smallest-first. If we flip it to reverse in-order (right, node, left), we visit largest-first instead.

We keep an accumulator acc starting at 0. At each node we do acc += node.val and then overwrite node.val = acc. Because we have already visited every key bigger than this one, acc holds exactly "this key plus all larger keys".

It works in a single pass and updates the tree in place — no extra sorting or arrays needed.

Example on BST built from [2,1,3]: we hit 3 first (acc = 3), then 2 (acc = 5), then 1 (acc = 6), producing values [5,6,3].

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