The problem
The diameter of a binary tree is the number of edges on the longest path between any two nodes (the path does not have to pass through the root). Return it.
Input: [1, 2, 3, 4, 5] Output: 3 (path 4 → 2 → 1 → 3)
Picture it
Picture walking between two leaves of a tree. Any such walk goes up to some highest node and back down. So at every node, the longest walk that bends there is (depth of left side) + (depth of right side). We compute depths bottom-up and keep the biggest bend we’ve seen anywhere.
How to recognise it
- The input is a binary tree and the question is about the longest path between any two nodes.
- The path may bend at some node: up one side, through the node, down the other. It does not have to pass through the root.
- Each node needs its children's heights, which a bottom-up depth-first search (DFS: follow one branch to the bottom before trying the next) already computes.
- The answer counts edges, not nodes. Up to 10^4 nodes, so aim for one visit per node.
Start with brute force
Every path has one highest node where it bends. For each node, the longest path bending there is height(left) + height(right). Compute that at every node with a separate height function and keep the best.
def height(node):
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
def diameter_brute(root):
if not root:
return 0
through = height(root.left) + height(root.right)
return max(through, diameter_brute(root.left), diameter_brute(root.right))
Each height call walks a whole subtree, and every node is walked again for each of its ancestors. That is O(n log n) on a balanced tree and O(n²) on a chain: about 5 × 10^7 steps for 10^4 nodes.
From brute force to the idea
- Find the waste. Heights are recomputed from scratch at every ancestor, although a node's height never changes.
- Compute height once, bottom-up. A post-order DFS (children before the node) gets
landr, the heights of the two subtrees, and returns1 + max(l, r)to its parent. - Record the bend on the way. While
landrare in hand,l + ris the number of edges on the longest path bending at this node:ledges down the left,rdown the right. Keep the largest inbest. - Return one thing, record another. The function returns a height (a path that can still be extended upwards) but records a diameter (a path that bends and cannot).
nonlocal bestlets the inner function update the outer variable.
This is the key idea: one DFS returns heights, and at each node l + r is a candidate answer.
The key idea
One DFS returning height; at each node update best = max(best, leftHeight + rightHeight). O(n).
Python solution
def diameter(root):
best = 0
def depth(node):
nonlocal best
if not node:
return 0
l, r = depth(node.left), depth(node.right)
best = max(best, l + r) # path that bends at this node
return 1 + max(l, r)
depth(root)
return bestIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n log n) balanced, O(n²) chain: heights recomputed for every ancestor | O(h): recursion only, h is the height |
| One DFS (shown code) | O(n): each node visited once, O(1) work | O(h): one stack frame per level, h = n for a chain |
Edge cases
- Single node: returns 0 (no edges).
- Two nodes: returns 1.
- Empty tree: returns 0, though LeetCode guarantees at least one node.
- Longest path avoids the root (
[1, 2, null, 3, 4, 5, null, 6]): returns 4 (6 → 4 → 2 → 3 → 5); the root contributes only 3. - Chain of n nodes: returns n − 1.
- Very deep tree: a chain of about 1,000 nodes hits Python's default recursion limit (
RecursionError); LeetCode allows 10^4 nodes. Use an explicit stack if that matters.
Common mistakes
- Returning
height(root.left) + height(root.right)only, which assumes the path passes through the root. - Returning
l + rfrom the recursion: a parent cannot extend a path that already bends. - Counting nodes instead of edges, which is off by one.
- Forgetting
nonlocal, sobest = max(...)raisesUnboundLocalError.
Return the number of edges on the longest path where every node has the same value (LeetCode 687). For [5, 4, 5, 1, 1, null, 5] the answer is 2 (the three 5s). Describe your approach, then write it if you like.
Compare with our answer
Same shape, but an arm only continues into a child with the same value. Each call returns the longest same-value arm going down from the node; at each node, the two arms added together are a candidate.
def longest_univalue_path(root):
best = 0
def arm(node):
nonlocal best
if not node:
return 0
l, r = arm(node.left), arm(node.right)
l = l + 1 if node.left and node.left.val == node.val else 0
r = r + 1 if node.right and node.right.val == node.val else 0
best = max(best, l + r)
return max(l, r)
arm(root)
return best
Time O(n), space O(h).
A strong answer mentions: always recursing into both children (a mismatched child may still hold a long path), cutting the arm to 0 on a mismatch, and recording l + r while returning max(l, r).
1. In a tree of cities joined by roads (no cycles), you must find the two cities farthest apart. Which approach fits best?
The farthest pair bends at some city, so the two longest arms below it give a candidate, and one DFS finds all candidates in O(n). The deepest level from the root misses paths that bend elsewhere, and separate heights repeat work.
2. Why does the shown function return 1 + max(l, r) but record l + r?
A path through the parent can use only one branch below a child, so the child reports its longest single arm. The bent path l + r is complete at this node and is only compared with the best so far.
3. A learner returns height(root.left) + height(root.right) as the diameter. Which tree is now answered wrongly?
In the last tree the longest path 6 → 4 → 2 → 3 → 5 bends at node 2, not at the root, so the root-only formula gives 3. In the other trees the longest path happens to pass through the root.
Score 60% or more and the lesson is marked complete.