Pattern Recognition Drill
Easy Advanced Trees
The Problem
Find the diameter (longest path between any two nodes).
What approach would you use?
Think about it before scrolling down.
Height recursion, update global max = left_h + right_h at each node. O(n).
Common Trap
The diameter doesn't necessarily pass through the root! Must check at every node.