DP on Trees
You've done DP on arrays and grids. Trees add a new dimension: states live at nodes, not indices.
Lessons
1. Intro
The Goal
2. Vocabulary - Subtree
The building block
3. The Tree DP Pattern
Dp[node] from children
4. Why Post-Order?
Children before parents
5. Quiz: Tree DP Basics
Knowledge check
6. Tree Diameter - Problem Statement
CSES 1131
7. Tree Diameter - Key Observation
Paths pass through nodes
8. Tree Diameter - State Design
Deepest path down
9. Tree Diameter - Implementation
Single DFS
10. Tree Diameter - Walkthrough
Tracing the algorithm
11. Challenge: Finding the Actual Path
Reconstructing the diameter
12. Quiz: Tree Diameter
Knowledge check
13. LeetCode 337 House Robber III - Problem Statement
LeetCode 337
14. LeetCode 337 House Robber III - Key Observation
Rob or skip each node
15. LeetCode 337 House Robber III - State Design
Two values per node
16. LeetCode 337 House Robber III - Implementation
Return a pair
17. LeetCode 337 House Robber III - Walkthrough
Tracing the two-state DP
18. Challenge: Three States
Extending to more states
19. Quiz: House Robber III
Knowledge check
20. Rerooting Technique
Why rerooting?
21. LeetCode 834 Sum of Distances in Tree - Problem Statement
LeetCode 834
22. LeetCode 834 Sum of Distances in Tree - Key Observation
Moving the root
23. LeetCode 834 Sum of Distances in Tree - Two Passes
Down then up
24. LeetCode 834 Sum of Distances in Tree - Implementation
The formula
25. LeetCode 834 Sum of Distances in Tree - Walkthrough
Tracing rerooting
26. Quiz: Rerooting Complexity
Understanding the efficiency
27. LeetCode 124 Binary Tree Maximum Path Sum - Problem Statement
Classic tree DP problem
28. LeetCode 124 Binary Tree Maximum Path Sum - Implementation
Handling negative values
29. Quiz: Maximum Path Sum
Understanding the transitions
30. LeetCode 310 Minimum Height Trees - Problem Statement
Finding centroids
31. LeetCode 310 Minimum Height Trees - Implementation
Topological peeling
32. LeetCode 1448 Count Good Nodes in Binary Tree - Problem Statement
Path maximum tracking
33. LeetCode 1448 Count Good Nodes in Binary Tree - Implementation
Top-down DFS pattern
34. Quiz: Top-Down vs Bottom-Up
Choosing the right direction
35. LeetCode 968 Binary Tree Cameras - Problem Statement
Minimum vertex cover variant
36. LeetCode 968 Binary Tree Cameras - State Transitions
Three-state DP
37. LeetCode 968 Binary Tree Cameras - Implementation
Post-order with state
38. Quiz: Tree Cameras Intuition
Why this greedy works
39. Pattern - Tree DP State Design
Designing effective states
40. Challenge: DP on DAGs
Generalizing beyond trees
41. Challenge: Tree DP with Queries
Preprocessing for fast queries
42. What's Next
Preview of Digit DP
43. Section Recap
What we learned
Practice Problems
Perfect intro to tree DP state propagation
Classic rerooting technique for all nodes
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Classic rerooting DP. Find node minimizing edge reversals to reach all others.
Count vertex pairs at distance k. Fundamental tree DP with path counting.
Maximize sum of subtree sizes during traversal. Beautiful rerooting application.
Maximize weighted distance sum from chosen root. Rerooting with contribution analysis.
Choose 3 nodes maximizing covered edges. Tree diameter extension problem.
Max path value with node values and edge costs. Tree path DP with pruning.
Max sum path in binary tree. Classic interview problem teaching path vs subtree distinction.
Minimum cameras to monitor all nodes. Tree DP with 3 states per node.
Longest path with constraint on adjacent nodes. Tree DP combining two best children.
Find diameter using interactive queries. Tree structure deduction.
Find max non-overlapping segments with equal sums. Greedy + interval selection.
Choose k components maximizing average sum. Tree DP with greedy selection.
Count independent sets on a tree - foundational tree DP with take/skip pattern.
Paint subtrees black with constraints - teaches rerooting technique for all-nodes answers.