Problem Statement
House Robber III
A thief wants to rob houses, but the houses are arranged as a binary tree. A binary tree is a structure where each house can have up to two houses hanging below it, a left one and a right one. A house with houses below it is called the parent, and the houses below it are its children. The rule: if you rob a house, you cannot rob the houses directly above or directly below it (the parent and its children), because they share an alarm. Your goal is to rob the largest total amount of money without ever robbing two connected houses. The key idea is that at every house you face one of two choices. You can rob this house, in which case you must skip its children. Or you can skip this house, in which case you are allowed to rob its children, but you are not forced to. To make the best choice, every house tells its parent two numbers: the best total if this house is robbed, and the best total if this house is skipped. Passing both numbers up the tree is what makes this fast.
Signals to notice
Brute force first
Try all subsets of non-adjacent nodes. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
DFS returning two values per node: (rob this node, skip this node). Rob = node.val + skip(left) + skip(right). Skip = max(rob, skip) of left + max(rob, skip) of right. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on root=[3,2,3,null,3,null,1] (root 3; left 2 with right-child 3; right 3 with right-child 1)
dfs(null) base case anywhere -> returns (0,0) for missing children Leaf 3 (under node 2): rob=3+0+0=3, skip=0 -> (3,0) Node 2 (left.skip): rob=2+0+0=2, skip=max(0,0)+max(3,0)=0+3=3 -> (2,3) Leaf 1 (under right 3): rob=1+0+0=1, skip=0 -> (1,0) Node 3 (right): rob=3+0+0=3, skip=max(0,0)+max(1,0)=0+1=1 -> (3,1) Root 3: rob=3 + left.skip(3) + right.skip(1) = 7, skip=max(2,3)+max(3,1)=3+3=6 -> (7,6) return max(dfs(root)) = max(7,6) = 7
What must stay true
Each node has two choices: rob it (can't rob children) or skip it (children can be robbed or skipped). The dual return value lets the parent make the optimal choice. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
dfs(node): if node is null: return (0, 0) # (rob, skip) L = dfs(node.left); R = dfs(node.right) rob = node.val + L.skip + R.skip skip = max(L) + max(R) return (rob, skip) answer = max(dfs(root))
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Using memoization with node references — works but the dual-return DFS is cleaner. Also, not returning both values forces redundant subtree computation. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.