Subtree DP
Processing trees from leaves to root. Aggregating subtree values. Include/exclude patterns and path optimization.
Lessons
1. Intro
The Goal
2. Trees as Recursive Structures
Each subtree is a tree
3. What is Subtree DP
Bottom-up computation on trees
4. DFS for Tree DP
Post-order traversal pattern
5. Example: Count Subtree Sizes
Simplest aggregation problem
6. Quiz: Basic Tree DP
Knowledge check
7. State Definition on Trees
What does dp[node] represent
8. Aggregating Child Values
Sum, max, count patterns
9. Time Complexity of Tree DP
Linear in node count
10. Rooted vs Unrooted Trees
Picking a root matters
11. CSES 1674 Subordinates - Problem Statement
CSES 1674
12. CSES 1674 Subordinates - Core Idea
Subtree size minus one
13. CSES 1674 Subordinates - Recurrence
Sum of child subtrees
14. CSES 1674 Subordinates - Algorithm
Single DFS pass
15. CSES 1674 Subordinates - Implementation
Code with adjacency list
16. CSES 1674 Subordinates - Walkthrough
Example tree trace
17. CSES 1674 Subordinates - Lessons
Subtree aggregation
18. Quiz: Subordinates Problem
Knowledge check
19. Include/Exclude Pattern
Two states per node
20. Include/Exclude Transitions
Combining child states
21. LeetCode 337 House Robber III - Problem Statement
LeetCode 337
22. LeetCode 337 House Robber III - State Definition
Two values per node
23. LeetCode 337 House Robber III - Recurrence
Include or exclude logic
24. LeetCode 337 House Robber III - Base Case
Null nodes return zero
25. LeetCode 337 House Robber III - Implementation
DFS returning pair
26. LeetCode 337 House Robber III - Walkthrough
Example tree trace
27. LeetCode 337 House Robber III - Lessons
Include/exclude on trees
28. Quiz: Include/Exclude Pattern
Knowledge check
29. Path Problems on Trees
Paths through nodes
30. Combining Paths from Children
Pick two best branches
31. LeetCode 124 Binary Tree Maximum Path Sum - Problem Statement
LeetCode 124
32. LeetCode 124 Binary Tree Maximum Path Sum - State Definition
Max downward path from node
33. LeetCode 124 Binary Tree Maximum Path Sum - Core Idea
Path through node vs from node
34. LeetCode 124 Binary Tree Maximum Path Sum - Handling Negatives
Skip negative branches
35. LeetCode 124 Binary Tree Maximum Path Sum - Algorithm
DFS with global max
36. LeetCode 124 Binary Tree Maximum Path Sum - Implementation
Code with global variable
37. LeetCode 124 Binary Tree Maximum Path Sum - Walkthrough
Example tree trace
38. LeetCode 124 Binary Tree Maximum Path Sum - Lessons
Two values pattern
39. Quiz: Path Problems
Knowledge check
40. Rerooting Technique Preview
Computing for all roots
41. Common Mistakes in Tree DP
What breaks your solution
42. Tree DP vs Graph DP
Why trees are simpler
43. When to Use Subtree DP
Problem recognition patterns
44. Section Recap
What we learned