Approach Summary
DFS returns height of each subtree. At each node, diameter candidate = left height + right height. Track global max.
How to Recognize This Pattern
- Longest path may not pass through root
- Diameter = max(left_depth + right_depth) over all nodes
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
Tags
Tree DFS Binary Tree