DP on Trees
You've done DP on arrays. Now states live at tree nodes. Solve Binary Tree Max Path Sum and learn how to aggregate child results at each vertex.
Lessons
1. Introduction to DP on Trees
Aggregate from subtrees
2. What Tree DP Solves
Diameters, paths, and matchings
3. When to Use Tree DP
No cycles, natural recursion
4. Problem - Binary Tree Max Path Sum
LC 124 - any path, max sum
5. Binary Tree Max Path Sum - Why Naive Fails
The bend point insight
6. Binary Tree Max Path Sum - Defining the DP
Return vs update: what's the difference?
7. Binary Tree Max Path Sum - Transition
max(0, child) avoids negatives
8. Binary Tree Max Path Sum - Base Cases
Null = 0, leaf = its value
9. Binary Tree Max Path Sum - Implementation
Global update inside DFS
10. Binary Tree Max Path Sum - Time and Space
O(n) time, O(h) space
11. Binary Tree Max Path Sum - Edge Cases
All negative? Skewed tree?
12. Lessons from Binary Tree Max Path Sum
Return one direction, update both
13. Problem - Tree Distances II
CSES - distance sum per node
14. Tree Distances II - Why Naive Fails
Reroot in O(1), not O(n)
15. Tree Distances II - Defining the DP
Subtree size and subtree sum
16. Tree Distances II - Transition
Moving root flips distances
17. Tree Distances II - Base Cases
First DFS from arbitrary root
18. Tree Distances II - Implementation
Two DFS passes, O(n) total
19. Tree Distances II - Time and Space
O(n) beats naive O(n²)
20. Tree Distances II - Edge Cases
Star graph vs path graph
21. Lessons from Tree Distances II
Reroot when answer depends on root
22. Problem - Distance in Tree
CF 161D - pairs at distance k
23. Distance in Tree - Why Naive Fails
Combine depths across subtrees
24. Distance in Tree - Defining the DP
cnt[d] = nodes at depth d
25. Distance in Tree - Core Logic
Match d and k-d across children
26. Distance in Tree - Implementation
Small-to-large for O(n log n)
27. Lessons from Distance in Tree
Depth counting, not pair enumeration
28. Problem - Tree Diameter
LC 543 - longest path in edges
29. Tree Diameter - Solution
leftDepth + rightDepth through node
30. Tree Diameter - Complexity
O(n) single pass
31. Problem - Tree Painting
CF 1187E - maximize paint score
32. Tree Painting - Solution
Sum of subtree sizes
33. Tree Painting - Rerooting Formula
score[v] = score[u] + n - 2*size[v]
34. Problem - Tree Matching
Maximum matching in tree
35. Tree Matching - Solution
dp[v][matched] or dp[v][unmatched]
36. Tree Matching - Greedy Solution
Greedy from leaves up
37. Problem - Binary Tree Cameras
LC 968 - minimum cameras
38. Binary Tree Cameras - Solution
Three states: uncovered, covered, has camera
39. Quiz: Tree DP Patterns
Which subtree pattern is this?
40. Quiz: Tree DP Edge Cases
Single node, empty tree
41. Common Mistakes in Tree DP
Post-order for bottom-up
42. Problem - Longest Path With Different Adjacent Characters
LC 2246
43. Longest Path With Different Adjacent Characters - Implementation
Solution approach
44. Section Recap
From path sum to rerooting