The O(n) Club: House Robber III: Binary Trees, Burglaries & Existential Dread

The O(n) Club: House Robber III—Binary Trees, Burglaries & Existential Dread

⚡ TL;DR

You’re breaking into a mansion that’s weirdly shaped like a binary tree. Every room (node) holds cash, but robbing it means your getaway alert chain disables both children for the night. No, you can’t just brute-force every possibility unless your runtime is sponsored by a tortoise. Smart approach? DP on trees, passing up both ‘rob’ and ‘skip’ options for each node.

// For each node, return [loot if robbed, loot if skipped]
int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] left = dfs(node.left), right = dfs(node.right);
    int rob = node.val + left[1] + right[1];
    int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return new int[]{rob, skip};
}

🧠 How Devs Usually Mess This Up

Most folks try to enumerate every possible robbery route—like a burglar who’s watched too much ’24’ and not enough about recursion. This tank-sized brute force approach explodes exponentially: soon, you’re out of RAM and faith. And don’t forget—parent-child links matter, not “all neighbors.” Trees aren’t arrays, Chandler.

Also, if you’re only memoizing the max take per node—congrats, you’re about to double-count or skip lucrative paths. You need both rob and skip options at every branch, or it’s like baking a cake and forgetting half the eggs.

🔍 What’s Actually Going On

Welcome to the real heist. Each node stands at a binary crossroads:

• Rob it? Neither child can be hit this round, but you get grandkid options.
• Skip it? Every child can decide for themselves—true distributive burglary.
• Send both results (loot if robbed & loot if skipped) up as a tidy array.
• At the root, whoever’s richer—robbed or skipped—wins.

Classic tree DP is doing all the recursion heavy-lifting here. You get optimal loot without ever robbing the same sub-mansion twice.

🛠️ PseudoCode

• For each node, call DFS and return [max-rob, max-skip]:
• Base: null → [0, 0]
• Rob: node.value + left[1] + right[1]
• Skip: max(left[0], left[1]) + max(right[0], right[1])
• Return that up the tree.
• Once you’re at the top, take the richer of your two life choices.

💻 The Code

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }
    // int[0]=rob, int[1]=skip
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int rob = node.val + left[1] + right[1];
        int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, skip};
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Leaf nodes, null roots, and negative cash: Sometimes the best move is to rob no one. (Your criminal empire forgives you.)
• Only tracking one max: Oops. You just sabotaged a heist. Always return loot-for-both-choices up the DP call chain.
• Complexity: Brute force is exponential agony. Tree DP is O(n)—just one rational trip across the tree, no coffee IV required.

🧠 Interviewer Brain-Tattoo

“In tech, as in burglary, skipping the root might land you the jackpot. Don’t trust greedy algorithms unless you hate getting paid.”