House Robber III (Tree)
Each node returns two values: (max if robbed, max if not robbed). If you rob this node, you can't rob its children. If you skip it, take the best of each child (robbed or not). Recurse from the root.
How It Works
House Robber III lifts the take-or-skip recurrence onto a binary tree where no two adjacent (parent-child) nodes may both be robbed. A post-order DFS returns a pair for every node: the best loot if this node is robbed, and the best if it is not. Robbing the node forces both children into their not-robbed values plus the node's own value; skipping the node lets each child independently choose its better option, so skipped = max(leftRobbed, leftSkipped) + max(rightRobbed, rightSkipped).
Each node is visited once and combines two constant-size child results, so the algorithm runs in O(n) time with O(h) recursion stack. Returning a small tuple of states per subtree — instead of memoizing on node identity — is the defining move of tree DP.
Step-by-Step Visualization
Code
static int rob(TreeNode root) {
int[] result = dfs(root);
return Math.max(result[0], result[1]);
}
static int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0}; // [rob, skip]
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int robThis = node.val + left[1] + right[1];
int skipThis = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{robThis, skipThis};
}Tips & Gotchas
Practice Problems
- 1House Robber III
- 2Binary Tree Maximum Path Sum
- 3Longest ZigZag Path in a Binary Tree
- 4Binary Tree Cameras
About the Tree DP Pattern
Run DP on a tree where each node's answer depends on its children's answers. Process leaves first (base cases), then compute internal nodes bottom-up. The DFS naturally handles the ordering.
The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.
Common Dynamic Programming Interview Problems
- Climbing Stairs
- Coin Change
- Longest Common Subsequence
- 0/1 Knapsack
- Edit Distance
- House Robber
- Longest Increasing Subsequence
- Word Break
Frequently Asked Questions
Why return two values per node instead of one?
A single 'best for this subtree' value hides whether the root was robbed, but the parent needs that fact to enforce the adjacency constraint. Returning (robbed, notRobbed) exposes exactly the information the parent's decision depends on, and nothing more.
Why is naive recursion with rob/skip branches slow here?
The naive version recomputes grandchildren subtrees along multiple paths, giving exponential blowup on deep trees. The post-order pair formulation computes each subtree exactly once, which is the tree analogue of converting overlapping recursion into a table.
How does this pattern extend to Binary Tree Cameras?
Cameras need three states per node — covered with a camera, covered without one, and not covered — because a node can be monitored by its parent. The same post-order skeleton applies; only the state set and combination rules grow.