Tree Diameter via DP
You'll learn how to compute the longest path between any two nodes in a tree using dynamic programming on subtrees.
The Core Idea
The diameter of a tree is the longest path between any two nodes, measured in number of edges. While you could check all pairs of nodes (expensive!), dynamic programming lets you solve this in a single tree traversal.
The key insight: the longest path in a tree either:
- Passes through the current node (connecting two subtrees), or
- Lies entirely within one of its subtrees.
For each node, compute two values:
- Height: longest path going down from that node
- Diameter candidate: longest path through that node (sum of two largest subtree heights)
Track the maximum diameter seen across all nodes as you go.
How It Works
Start from the leaves and work upward (post-order):
- Base case: A leaf has height 0, diameter 0
- Recursive step: For each node:
- Get heights of all children's subtrees
- Node's height = 1 + max(children's heights)
- Path through this node = sum of two largest children's heights + 2
- Update global diameter if this path is longer
This leverages subtree independence—each subtree's diameter is computed once and reused.
Why DP?
Without DP, you'd redundantly recompute paths. DP captures the optimal solution (longest path down) from each subtree, avoiding repeated work. This transforms an exponential problem into O(n) time.
Key Takeaway: Tree diameter is found by computing the maximum of all "paths through node X" values, where each uses DP-computed heights from subtrees below—leveraging overlapping subproblems and optimal substructure.