Diameter of Binary Tree
Return the length (in edges) of the longest path between any two nodes — it need not pass the root.
Open on LeetCode ↗02
Intuition
The longest path bends at some node: left depth + right depth through it. Compute depth recursively and, at every node, test leftDepth + rightDepth as a diameter candidate — one DFS answers both questions at once.
03
Approach
1
Depth is the helper
depth(node) = 1 + max(depth(left), depth(right)). That's the standard recursion.
2
Diameter rides along
While unwinding, each node knows both child depths — their sum is the best path bending there. Track the global max in a side variable.
3
Return depth, record diameter
The recursion's return value stays pure (depth); the answer is collected as a side effect — a common DFS pattern.
04
Solution & live demo
python
▶1class Solution:
▶2 def diameterOfBinaryTree(self, root):
▶3 self.best = 0
▶4 def depth(node):
▶5 if not node: return 0
▶6 l, r = depth(node.left), depth(node.right)
▶7 self.best = max(self.best, l + r)
▶8 return 1 + max(l, r)
▶9 depth(root)
▶10 return self.best
05
Edge cases
Single node
No edges → diameter 0.
Degenerate chain
Best 'bend' is at the top: one side deep, other 0 — equals the chain length.
06
Complexity
Time
O(n)
Space
O(h)
One post-order pass; h = tree height.