The problem
Return the length (in edges) of the longest path between any two nodes in a binary tree. The path may or may not pass through the root.
Stuck? Reveal hints one at a time
How to approach it
- 1Write a height(node) function returning 0 for null.
- 2At each node, the candidate diameter is leftHeight + rightHeight; update the running maximum.
- 3Return 1 + max(leftHeight, rightHeight) as this node’s height.
- 4The maximum seen anywhere is the diameter.
Key insight
Every path has a unique highest node — checking left+right height at EVERY node therefore considers every possible path exactly once.
The solution
Watch out for
- The diameter is measured in EDGES here; some variants count nodes (answer + 1).
- Returning the diameter from the recursion instead of the height is the classic mix-up.