The O(n) Club: BST to Greater Sum Tree: The Rich Get Richer (and So Do You)

The O(n) Club: BST to Greater Sum Tree — The Rich Get Richer (and So Do You)

⚡ TL;DR

Want every node in your BST to suddenly feel wealthier? Just replace its value with its own plus all values bigger than it. Easy—so long as you walk backward (right–root–left) and tote a running sum. If you try brute force, your next coffee will get cold before it finishes.

// (Anti-pattern) Brute force method
void badGreaterSum(TreeNode root) {
    List
<integer> vals = new ArrayList<>();
    storeInOrder(root, vals);
    updateWithSums(root, vals);
}
// Real fix? See below.
</integer>

🧠 How Devs Usually Mess This Up

There are basically three ways people slip on this banana peel:

• Using normal in-order (left–root–right): You visit the poor first, so your sum’s on the wrong side of history.
• Mixing this up with a prefix/suffix sum: This party’s only for people with wallets fatter than yours (or equally fat)—not those behind you in line.
• Neglecting your running sum’s initial value. (Hint: It should not be your salary last year. Start at 0.)

Worse: brute-force nested searching for sums. You’ll get O(n²) and flashbacks to your last infinite loop bug.

🔍 What’s Actually Going On

Imagine your BST is a prestige tech ladder. Big values (VPs, CEOs) live to the right. We’re updating each person’s title so it reflects their own value plus the bonuses of everyone bigger than them.
How? Easy: Traverse your org chart from the richest (rightmost) down, keeping a piggy bank (the running sum). Deposit each exec’s old salary as you pass, then hand the sum so far to the next employee.

If you accidentally traverse left first (classic), you’ll “bonus” the unpaid interns instead of the VPs. Yikes.

🛠️ PseudoCode

• Set up a running sum:

  int sum = 0;

  Because count starts at zero, like your optimism after reading legacy code.
• Do reverse in-order:

  void dfs(TreeNode n) {...}

  Always visit right child, then root, then left child.
• Visit right subtree:

  dfs(n.right);

  Bigger values deserve attention first.
• Update the node:

  n.val += sum;
  sum = n.val;

  Now your node is officially a “Greater Node.”
• Visit left subtree:

  dfs(n.left);

  Finally, the smaller folk get their new total. Isn’t trickle-down supposed to work like this?

💻 The Code

// Show time!
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}
 class Solution {
    int sum = 0;
    public TreeNode bstToGst(TreeNode root) {
        reverseInOrder(root);
        return root;
    }
    private void reverseInOrder(TreeNode node) {
        if (node == null) return;
        reverseInOrder(node.right);
        node.val += sum;
        sum = node.val;
        reverseInOrder(node.left);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Null roots: If the tree’s empty, so is your runtime headache. Just return null and move on.
• Non-BST inputs: Sneaking this code on a non-BST? You get comedic results (and not the funny kind).
• Stack overflow risks: Lopsided trees mean deep recursion. Interviewer not a recursion fan? Use a stack instead, if you like hand cramps.
• Real-world costs: O(n) time (one pass), O(h) stack (h = tree height). Space-efficient unless you’re allergic to recursion.

🧠 Interviewer Brain-Tattoo

“Don’t in-order from left. Be greedy—visit the bigwigs first. In BSTs as in life, you want the richest folks on your side before you head for the interns.”