Lesson 297
Tree DP
Post-order DFS · Subtree states · Rerooting
1:00How to solve tree problems with dynamic programming — post-order DFS, subtree states, and rerooting — all in O(n).
By the end, you can
- Explain the post-order tree-DP pattern and why it guarantees correct bottom-up computation.
- Compute subtree sizes in a single DFS using the recurrence `size(v) = 1 + sum of children sizes`.
- Trace the diameter algorithm, identifying which two child depths are combined at each node.
- Distinguish the diameter from the height of a tree and explain why the diameter path need not pass through the root.
- Apply the include/exclude state recurrence for max independent set on a tree.
- Explain why rerooting requires only two DFS passes and derive the O(1) per-edge update formula.
- Analyze when a tree problem requires one value per node versus a state vector, and choose the right representation.
Up next in String Algorithms, Advanced DP & Competitive Techniques
