Diameter of Binary Tree
Find the longest path between any two nodes, and learn the trick of returning one value while recording another
Problem Statement
Given the root of a binary tree, return the length of its diameter — the longest path between any two nodes, measured in edges.
The path does not have to pass through the root.
Input: root = [1, 2, 3, 4, 5]
Output: 3
1
/ \
2 3
/ \
4 5
Longest path: 4 → 2 → 5 ... or 4 → 2 → 1 → 3 (3 edges)Intuition
The tempting answer is depth(left) + depth(right) at the root. That is right for the example above — but only by luck.
Why the root is not always the answer
1
/
2
/ \
4 5
/ \
6 7
The longest path is 6 → 4 → 2 → 5 → 7, which is 4 edges.
It never touches the root.The problem says the path need not pass through the root, and this is the tree that punishes you for assuming it does.
So the diameter could be centred on any node. That suggests checking every node — computing depths at each one — which is O(n²).
The key insight
Every path has exactly one highest node — the top of its arch. For that node, the path length is depth(left) + depth(right).
So instead of asking "what is the diameter?", visit each node once and ask "what is the best path arching over me?" Keep the largest answer seen.
That turns O(n²) into O(n), because depth and diameter can be computed in the same pass.
The trick that makes it work
Here is the part worth slowing down on, because it is reused everywhere.
The recursion must produce two different things:
| Quantity | Who needs it | Nature |
|---|---|---|
| Depth of this subtree | The parent, to compute its own arch | Must be returned |
| Best arch seen anywhere | Only the final answer | Must be recorded |
You cannot return both from one recursive call — the parent's arithmetic requires the depth. So the depth goes in the return value, and the best arch goes into a variable held outside the recursion.
Why the parent cannot use the diameter
A parent building its own arch needs to know how far down each side reaches. That is depth.
The child's best diameter might be a path buried deep in a corner that never reaches the child's root — useless for extending upward. Depth is the only thing that composes.
The real-world version
Measure the longest corridor in a building where every room branches downward. Stand in each room and ask: how far can I reach going down the left wing, plus how far down the right wing? That is the longest corridor passing through this room.
Write it on a whiteboard if it beats the current record. Then tell your parent only the deeper of your two wings — because that is all they can build on.
Approach
Keep a best variable outside the recursion
It starts at 0 and only ever grows. This is where the answer accumulates.
Write a helper that returns depth
Empty subtree returns 0. Otherwise it returns 1 + max(left, right) — the same shape as Maximum Depth.
Before returning, record the arch
At each node, left + right is the path length in edges that arches over it. Update best if it is larger.
Note there is no +1 here. left + right already counts edges: going down left edges on one side and right on the other.
Return the depth, not the arch
The parent needs 1 + max(left, right). Returning the arch instead is the classic bug — it corrupts every calculation above.
Watch it run
Solution
class TreeNode:
def __init__(self, val: int = 0, left: "TreeNode | None" = None,
right: "TreeNode | None" = None):
self.val = val
self.left = left
self.right = right
def diameter_of_binary_tree(root: TreeNode | None) -> int:
"""Return the longest path between any two nodes, counted in edges."""
best = 0
def depth(node: TreeNode | None) -> int:
nonlocal best # without this, `best = ...` would create a local
if node is None:
return 0
left = depth(node.left)
right = depth(node.right)
# The longest path whose highest point is THIS node.
# No +1: left and right already count edges.
best = max(best, left + right)
# The parent needs depth, not diameter.
return 1 + max(left, right)
depth(root)
return bestTwo bugs that look almost identical
Returning the arch instead of the depth. return left + right compiles, runs, and gives wrong answers on any tree taller than two levels, because every ancestor then builds on a meaningless number.
Forgetting nonlocal in Python. Without it, best = max(...) creates a fresh local variable inside depth, the outer best never changes, and the function always returns 0. There is no error — just a silent zero.
JavaScript closures capture the outer variable automatically, so the second bug does not exist there.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
- Time — each node is visited exactly once. The naive "compute depth at every node" version would be
O(n²); computing depth and diameter together in one pass removes the repeated work. - Space — the recursion stack, one frame per level.
O(log n)for a balanced tree,O(n)for a chain.
Edge Cases
Related Problems
- Maximum Depth of Binary Tree — the depth helper, on its own
- Invert Binary Tree — the same skeleton, mutating instead of measuring
- Trees — why post-order is the right visit order here