House Robber III
Rob a binary tree of houses without robbing two linked ones: a post-order DFS returns, for every house, the best total if you rob it and if you skip it.
Problem Understanding
House Robber III: the houses form a binary tree, each holding some money. Robbing two directly linked houses (a parent and its child) on the same night alerts the police. Return the most money you can rob.
Example: [3,2,3,null,3,null,1] returns 7: rob the root 3 and the two grandchildren 3 and 1.
The Intuition: Two Answers per House
In House Robber each house only clashes with its neighbours in a line. Here a house clashes with its parent and its children, so solve each subtree twice:
- rob: this house is robbed, so both children must be skipped:
node.val + left.skip + right.skip. - skip: this house is left alone, so each child takes whichever of its two answers is better:
max(left) + max(right). - Compute children first (post-order), then the root's
max(rob, skip)is the answer.
Every node is visited once. This is dynamic programming on a tree, driven by a depth-first search; House Robber II is the circular variant of the original.
Interactive Walkthrough
Houses fill in from the leaves up; under each finished house is rob/skip. At the end the houses of one best plan turn green. Try Example 2, where skipping the root wins.
Dry Run Table
Input: [3,2,3,null,3,null,1] (root 3; left child 2 with right child 3; right child 3 with right child 1)
| House | rob | skip |
|---|---|---|
| leaf 3 (under 2) | 3 | 0 |
| 2 | 2 + 0 + 0 = 2 | 0 + max(3, 0) = 3 |
| leaf 1 | 1 | 0 |
| 3 (right child) | 3 + 0 + 0 = 3 | 0 + max(1, 0) = 1 |
| root 3 | 3 + 3 + 1 = 7 | max(2, 3) + max(3, 1) = 6 |
Answer: max(7, 6) = 7: rob the root and the two grandchildren.
The Solution Template
A post-order DFS returning a pair. C returns the pair through two out-parameters.
House Robber III Code
1var rob = function(root) {2 const dfs = (node) => {3 if (!node) return [0, 0];4 const [lRob, lSkip] = dfs(node.left);5 const [rRob, rSkip] = dfs(node.right);6 return [node.val + lSkip + rSkip, Math.max(lRob, lSkip) + Math.max(rRob, rSkip)];7 };8 return Math.max(...dfs(root));9};
Edge Cases & Common Mistakes
- Skip means "free", not "rob the children": when a house is skipped, each child picks the better of rob and skip; forcing the children to be robbed loses answers.
- Greedy by level: robbing alternate levels can miss mixed plans like
[2,1,3,null,4](answer 7). - Plain recursion without pairs or memo: recomputing grandchildren from every ancestor is exponential.
- Single house: the answer is its value.
- Zero-value houses: fine; robbing or skipping them changes nothing.
Summary
Post-order DFS returning (rob, skip) for each subtree: rob = val + left.skip + right.skip, skip = max(left) + max(right). The answer is max of the root's pair. O(n) time, O(h) space.
More practice: DSA interview questions with answers · patterns cheat sheet