Path Sums and Tree DP
You'll learn how to use dynamic programming to find optimal paths in trees—whether from root to leaf or between any two nodes.
The Core Idea
In tree DP, we often need to track values along paths. A path sum is the total of node values along some route through the tree. The challenge: there are exponentially many possible paths, but DP lets us compute optimal ones efficiently by building solutions bottom-up from subtrees.
Think of it like calculating the best hiking route through branching mountain trails. At each junction, you only need to remember the best path from each branch—you don't recalculate every possible route from scratch.
Two Common Path Types
Root-to-Leaf Paths
For each node, track the maximum (or minimum) sum ending at that node. Your recurrence combines the node's value with the best result from its parent.
Any-Node-to-Any-Node Paths
Here's where subtree independence shines. At each node, the best path through that node might:
- Stay within the left subtree
- Stay within the right subtree
- Connect left → node → right (forming an "arch")
Your DP state tracks the best "downward" path from each node, then at each step considers whether connecting two subtree paths through the current node beats your global answer.
The DP Pattern
- Define state: What's the best sum ending/starting at this node?
- Recurrence: Combine child results with current node value
- Base case: Null nodes contribute 0 (or negative infinity for max problems)
- Track global: Update the overall best as you traverse
This technique extends to counting paths with target sums, finding maximum product paths, or even paths with alternating up/down movements.
Key Takeaway: Path sum problems on trees leverage DP by storing optimal partial paths at each subtree, then combining them efficiently at parent nodes—avoiding exponential path enumeration.