House Robber III
Problem Statement
The houses form a binary tree. Each node contains money, and directly connected houses cannot both be robbed. Given the root, return the maximum amount of money that can be robbed without robbing any parent-child pair together.
Input
The root pointer of a binary tree where each node value is the money in that house.
Output
An integer: the maximum money that can be robbed without choosing adjacent parent-child nodes.
Constraints
- •
1 <= number of nodes <= 10^4 - •
0 <= Node.val <= 10^4 - •
The input is a binary tree
Examples
Example 1
root = [3,2,3,null,3,null,1]
7Example 2
root = [3,4,5,1,3,null,1]
9Learning Objectives
- Model each subtree with two values: rob this root or skip this root.
- Use postorder DFS so children are solved before the parent chooses.
- Explain the recurrence without relying on linear House Robber indexing.
- Connect binary-tree recursion to dynamic programming over subtrees.
Intuition
Pattern Recognition
The technique is subtree DP pair. The signal is a tree with a choose-or-skip constraint between a node and its children. A single value per subtree is not enough, because the parent needs to know two scenarios: what if this child is robbed, and what if this child is skipped?
So every node returns a pair [robThis, skipThis]. If you rob the current node, you must skip both children, so the value is the node money plus each child skip value. If you skip the current node, each child is free to choose its better option, so you add the maximum of each child pair. This is tree DP expressed through postorder recursion.
Common mistakes
- ×Using the linear House Robber recurrence and ignoring that a tree has two child subproblems.
- ×Returning only one best value from a child, which loses whether the child itself was robbed.
- ×Adding child robbed values when robbing the parent, which violates the adjacency rule.
- ×Trying to greedily rob larger-valued nodes without considering grandchildren.
Algorithm Explanation
Key idea
For each node, compute two answers for its entire subtree. robThis means the current node is robbed, so children must contribute their skip values. skipThis means the current node is skipped, so each child contributes the better of robbing or skipping that child. A postorder traversal guarantees both child pairs are ready before the parent pair is built.
Recursion walkthrough
Use [3,2,3,null,3,null,1]. The leaf 3 under node 2 returns [3, 0] because robbing it gives 3 and skipping it gives 0. Node 2 sees no left child and that right leaf pair, so robbing 2 gives 2, while skipping 2 lets the child contribute 3. It returns [2, 3].
The right child 3 with leaf 1 returns [3, 1]. At the root 3, robbing the root gives 3 + left.skip 3 + right.skip 1 = 7. Skipping the root gives max(2, 3) + max(3, 1) = 6. The final answer is 7.
Algorithm
- Define a postorder helper that returns [robThis, skipThis] for a subtree.
- For an empty node, return [0, 0].
- Recursively get the left child pair.
- Recursively get the right child pair.
- Compute robThis as the current value plus the skip values from both children.
- Compute skipThis as the sum of the better value from each child pair.
- Return the pair and take the maximum of the root pair as the final answer.
Solutions
Solution: Postorder subtree DP pair
Use this as the canonical solution. It is linear, does not need a hash map, and makes the parent-child compatibility rule explicit.
Let every subtree return two numbers. The first is the best total when the subtree root is robbed. The second is the best total when the subtree root is skipped. Build those two values from the already-solved child pairs.
Step-by-step
- Return [0, 0] for a missing node.
- Recursively solve the left child.
- Recursively solve the right child.
- If robbing the current node, add node.val plus the skip values from both children.
- If skipping the current node, add the better value from the left child and the better value from the right child.
- Return the two-value result to the parent.
- At the root, return the larger of robbing or skipping it.
O(n)
O(h)
Each node creates one constant-size pair; recursion stack height is **h**, which can be **n** for a skewed tree.
Java implementation
Dry Run
Sample input
root = [3,2,3,null,3,null,1]. Each row shows the pair returned after both children are processed.
| node | left pair | right pair | robThis | skipThis | returned pair |
|---|---|---|---|---|---|
| leaf 3 under 2 | [0, 0] | [0, 0] | 3 | 0 | [3, 0] |
| node 2 | [0, 0] | [3, 0] | 2 | 3 | [2, 3] |
| leaf 1 | [0, 0] | [0, 0] | 1 | 0 | [1, 0] |
| right node 3 | [0, 0] | [1, 0] | 3 | 1 | [3, 1] |
| root 3 | [2, 3] | [3, 1] | 7 | 6 | [7, 6] |
The root returns [7, 6], so the best valid robbery is 7 by robbing the root and the two grandchildren.
Interview Tips
Avoid saying only best subtree value because the parent needs compatibility information. Name the two returned values clearly: robThis and skipThis. Then derive the recurrence in words: robbing a node forces child skips, while skipping a node lets each child choose its better option. This explanation connects tree recursion directly to DP.
Likely follow-ups
- How would you reconstruct which nodes are robbed, not just the maximum amount?
- What changes if grandchildren also cannot both be robbed with a grandparent?
- How would the solution change for an n-ary tree?
- How is this related to the original House Robber problem on an array?
Similar Problems
Key Takeaways
- Tree DP often returns multiple values per node so the parent can make a compatible choice.
- Robbing a node combines with each child skip value.
- Skipping a node combines with the best option from each child.
- Postorder traversal is what makes the child DP pairs available before computing the parent pair.