The O(n) Club: Convert BST to Greater Tree—Because Your Nodes Have FOMO

The O(n) Club: Convert BST to Greater Tree—Because Your Nodes Have FOMO

⚡ TL;DR

Want every node in your BST to brag about all the higher values above them? Just march right-to-left and keep adding up the running total. Java does it in 7 lines, no extra baggage required:

// Don't: O(n^2) nested summing per node—your CPU will file for overtime
// Do:
int sum = 0;
void convert(TreeNode node) {
    if (node == null) return;
    convert(node.right);
    node.val += sum;
    sum = node.val;
    convert(node.left);
}

🧠 How Devs Usually Mess This Up

If you reached for an ArrayList or tried classic in-order, congrats, you’ve overcomplicated what could’ve been a two-coffee problem. Standard in-order (left, node, right) adds smaller values, leaving your Greater Tree feeling, well, lesser. Multiply that by an O(n^2) brute-force nested sum, and you’re basically hosting a memory leak party.

🔍 What’s Actually Going On

Picture your BST as a fancy office food chain (literally). The rightmost node? That’s the CEO, grabbing all the snacks. Everyone else to the left is hoping for leftovers. To tally each staffer’s “snacks plus what the execs claimed,” begin at the right, accumulate as you pass each one, and hand down the sum—like a retro company memo no one asked for.

Why not extra arrays? Because reverse in-order taps the BST’s ordering magic. You get the next-greatest value every single step, updating nodes as you stroll leftwards—no lookbacks or awkward re-traversals. Minimal state. Maximum cleverness.

🛠️ PseudoCode

• Initialize sum = 0
• Define a function traverse(node):
• If node == null, bail
• traverse right child (traverse(node.right))
• Add sum to current node’s value
• Update sum = node.val
• traverse left child (traverse(node.left))
• Start: traverse(root)

And your nodes will be instantly richer (no capital gains tax required).

💻 The Code

// Node definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 // Solution
class Solution {
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        traverse(root);
        return root;
    }
    private void traverse(TreeNode node) {
        if (node == null) return;
        traverse(node.right);
        node.val += sum;
        sum = node.val;
        traverse(node.left);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Normal in-order? Oops, you added up all the wrong values. Only the right knows best.
• Map or array? You’re burning extra space for no reason. Recursion and a sum variable handle it in-place.
• Edge cases: Null trees and lonely single nodes work fine—they just want love, not drama.
• Time: O(n) for actual node visits. Accept no quadratic substitutes.
• Space: O(h) recursion stack—unless you flatten the tree into a spaghetti nightmare.

🧠 Interviewer Brain-Tattoo

If you wouldn’t reverse in-order, your BST will never stop living in the shadow of its richer, right-hand siblings. Let the wealth flow left.