House Robber III – Solution & Complexity
Solution Walkthrough
1. Understand the constraint on the tree
- Robbing a house forbids robbing its parent and its direct children.
- At every node you face a binary choice: rob this node (and skip its children) or skip it (and freely choose within each child).
- This is the linear House Robber idea lifted onto a tree.
2. Start from the naive recursion
- If you rob the current node, add its value plus the best of each grandchild subtree.
- If you skip it, add the best of each child subtree.
- Take the larger of the two. This is correct but recomputes grandchildren over and over.
3. Return two values per node
- Have each DFS call return a pair: the best loot if this node is robbed and the best if it is not.
robbed = node.val + skip(left) + skip(right)(children must be skipped).notRobbed = max(child options) summed over both children.
4. Optimal single postorder pass
- Combine both children's pairs in
O(1)at each node, with no recomputation. - The answer is the better of the two options at the root.
5. Dry run
Trace root = [3,2,3,null,3,null,1].
| node | (rob, skip) |
|---|---|
leaf 3 (under left 2) | (3, 0) |
left child 2 | (2, 3) |
leaf 1 (under right 3) | (1, 0) |
right child 3 | (3, 1) |
root 3 | (3 + 3 + 1, max(2,3)+max(3,1)) = (7, 6) |
The answer is max(7, 6) = 7.
6. Common mistakes and follow-ups
- Only tracking a single number per node, which forces expensive grandchild recomputation.
- When robbing a node, adding the child's robbed value instead of its skipped value.
- Forgetting that an empty tree returns
0. - Follow-up: how would you also return which houses were robbed?
7. Edge cases to test mentally
- An empty tree yields
0; a single node yields its own value. - A straight chain alternates robbed/skipped levels.
- Sometimes robbing every leaf beats robbing the root plus grandchildren, so always compare both options at the root.
8. Final full solution and complexity
A single postorder DFS returns each node's (robbed, skipped) best totals and combines children in O(1). Time is O(n) and stack space is O(h) for tree height h.
