Tree DP: take or skip this node
Each node returns two values: best if taken, best if skipped.
take = node + skip(children); skip = max over each child of take/skip.
01The intuition
Start with what you would do by hand
Houses are arranged as a tree, each with some money: 3 at the top; 2 and 3 below; 3 under the left 2 on its right; 1 under the right 3 on its right. A thief cannot rob two houses that are directly joined. What is the most he can take? By hand you would try combinations: rob the root 3 and the two bottom houses 3 and 1, total 7; or skip the root and rob 2 and 3 from the middle, total 5; or 2 and the bottom 3... The best is 7.
With 5 houses you can try every subset. With n houses there are 2n subsets; for 40 houses, a trillion. Trying them all is hopeless, and a greedy rule like "always rob the richest" fails: sometimes two moderate houses beat one rich one between them.
Build the structure, one piece at a time
The tree is the structure. What we add is two numbers per node, computed bottom-up like every post-order fold.
Piece one: for each node, rob[v] = the most you can take from v's subtree if you rob v. If you rob v, you cannot rob its children, so you must skip both: rob[v] = value(v) + skip[left] + skip[right].
Piece two: skip[v] = the most you can take from v's subtree if you do not rob v. Then each child is free to be robbed or skipped, whichever is better for it: skip[v] = max(rob[left], skip[left]) + max(rob[right], skip[right]).
Piece three: a missing child contributes 0 to both. The final answer is max(rob[root], skip[root]).
| Node (value) | rob | skip |
|---|---|---|
| bottom 3 | 3 + 0 + 0 = 3 | 0 |
| left 2 | 2 + skip(3) = 2 | max(3, 0) = 3 |
| bottom 1 | 1 | 0 |
| right 3 | 3 + skip(1) = 3 | max(1, 0) = 1 |
| root 3 | 3 + 3 + 1 = 7 | max(2, 3) + max(3, 1) = 6 |
Answer: max(7, 6) = 7, and the table shows exactly which choice was better at every house.
Why it is correct
The key observation is that the decision at a node only interacts with its children: whether you rob v constrains the children, and nothing else. So the best for v's subtree depends only on the two numbers from each child, never on the grandchildren directly, because those are already folded into the children's numbers.
rob[v] = val(v) + skip[l] + skip[r], skip[v] = max(rob[l], skip[l]) + max(rob[r], skip[r])
Both equations consider every legal plan for the subtree: a plan either robs v (first formula, children forced skipped) or does not (second formula, children free). Leaves are correct by inspection, and if the children's pairs are correct the parent's pair is correct, so the root's pair is correct.
Why it is fast
Each node does two additions and two maxima on four numbers from its children: O(n) time, O(h) stack. Compared with 2n subsets, for 40 houses that is 40 operations instead of a trillion. The trick that made it possible is returning a pair instead of a single number; one number would lose the information about whether the child was robbed.
How to recognise it in an interview
Choices on a tree where picking a node restricts its neighbours: "no two adjacent", "place cameras so every node is watched", "move coins so each node has one". Say: "Each node returns a small set of values, one per state it can be in, computed from its children's values." House Robber III is the two-state version above. Binary Tree Cameras uses three states per node: has a camera, is covered, is not covered. Distribute Coins in Binary Tree returns the surplus of coins in the subtree, and the moves are the absolute surpluses summed over all edges.
02The idea in one line
Each node returns two values: best if taken, best if skipped.
Reach for it when: House Robber III, maximum independent set, cameras, coins distribution.
Cost: O(n) time.
03The walk-through, step by step
The video works one example: House Robber III on [3,2,3,null,3,null,1]. These are its captions in order, so you can follow without the video or check a step you missed.
- Two values per node: best if we rob it, best if we skip it
- Node 3: ask the children first
- Node 2: ask the children first
- Node 3: ask the children first
- Node 3: rob = 3, skip = 0
- Node 2: rob = 2, skip = 3
- Node 3: ask the children first
- Node 1: ask the children first
- Node 1: rob = 1, skip = 0
- Node 3: rob = 3, skip = 1
- Node 3: rob = 7, skip = 6
- Root: max(rob 7, skip 6) = 7
- Each node combines two numbers from each child: O(n)
04Asked at Google
6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| House Robber III | Medium | 27 | last 6 months |
| Maximum Number of K-Divisible Components | Hard | 24 | |
| Distribute Coins in Binary Tree | Medium | 21 | last 6 months |
| Number of Good Leaf Nodes Pairs | Medium | 18 | |
| Binary Tree Cameras | Hard | 13 | last 6 months |
| Minimum Cost Tree From Leaf Values | Medium | 8 |
05Related patterns
Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Serialize / deserialize by BFS.