Diameter of Binary Tree
Problem Statement
Given the root of a binary tree, return the length of the diameter of the tree. The diameter is the number of edges on the longest path between any two nodes. The path may or may not pass through the root.
Input
The root pointer of a binary tree, or null for an empty tree.
Output
An integer: the number of edges on the longest path between any two nodes.
Constraints
- •
0 <= number of nodes <= 10^4 - •
-100 <= Node.val <= 100
Examples
Example 1
root = [1,2,3,4,5]
3Example 2
root = [1,2]
1Example 3
root = []
0Learning Objectives
- Recognise diameter as a best path anywhere in the tree, not necessarily through the root.
- Use postorder recursion to compute child heights before combining them at the current node.
- Separate the value returned upward from the global best answer tracked across all nodes.
- Avoid confusing edge count with node count when computing the path through a node.
Intuition
Pattern Recognition
The signal is a tree question asking for the best path anywhere, while each node can only learn about that path after seeing both subtrees. That is a postorder aggregation problem: ask the left child for a height, ask the right child for a height, then combine those two answers at the current node.
The important template is return one value up, track a global best. The value returned upward is the height of this subtree, because the parent can extend only one downward branch. The global best stores a different value: the longest path that bends through the current node, which is leftHeight + rightHeight.
Common mistakes
- ×Returning the diameter upward instead of returning the height the parent needs.
- ×Counting nodes in the final answer even though the problem asks for edges.
- ×Only checking paths through the root and missing a larger diameter inside a subtree.
- ×Recomputing subtree heights from scratch at every node, which wastes time.
Algorithm Explanation
Key idea
Use a postorder DFS. Let height(node) return the number of nodes on the longest downward chain starting at node. A null child has height 0. After computing leftHeight and rightHeight, the best path that passes through this node has leftHeight + rightHeight edges, so update a global diameter. Then return 1 + max(leftHeight, rightHeight) upward.
Recursion walkthrough
For [1,2,3,4,5], visit leaves first. Node 4 has no children, so it returns height 1 and contributes path length 0. Node 5 does the same. At node 2, the left and right heights are both 1, so the path through 2 has length 2: 4 -> 2 -> 5. The global diameter becomes 2, while node 2 returns height 2 upward to node 1.
Node 3 returns height 1. At node 1, the left height is 2 from subtree 2, and the right height is 1 from node 3. The path through 1 has length 3, so the global diameter becomes 3. Node 1 returns height 3, but the answer is the global diameter, not that returned height.
Algorithm
- Initialise a global diameter to 0.
- Define a recursive helper that returns subtree height.
- For a null node, return height 0.
- Recursively compute leftHeight and rightHeight.
- Update diameter with leftHeight + rightHeight because that is the best path through the current node.
- Return 1 + max(leftHeight, rightHeight) so the parent can extend one side.
- After DFS finishes, return the global diameter.
Solutions
Solution: Postorder height with global diameter
Use this as the canonical interview solution. It computes every subtree height once and keeps the best cross-node path in a global variable.
Run a postorder DFS where each node returns its height to its parent. During the unwind, update a global diameter with the path that goes from the deepest node in the left subtree, through the current node, to the deepest node in the right subtree.
Step-by-step
- Start diameter at 0.
- Return 0 from the helper when the current node is null.
- Recursively compute the left and right heights.
- Update diameter with leftHeight + rightHeight.
- Return 1 + max(leftHeight, rightHeight) as the height available to the parent.
- Return diameter after all nodes have been processed.
O(n)
O(h)
Each node is visited once; recursion uses stack space proportional to tree height.
Java implementation
Dry Run
Sample input
root = [1,2,3,4,5]. Heights use null = 0, so leftHeight + rightHeight counts edges through a node.
| node | leftHeight | rightHeight | returned height | globalBest |
|---|---|---|---|---|
| 4 | 0 | 0 | 1 | 0 |
| 5 | 0 | 0 | 1 | 0 |
| 2 | 1 | 1 | 2 | 2 |
| 3 | 0 | 0 | 1 | 2 |
| 1 | 2 | 1 | 3 | 3 |
The root returns height 3, but the answer is the separate global best 3, representing a path with 3 edges.
Interview Tips
Say the separation out loud: the helper returns height, while the answer variable stores diameter. That prevents the most common bug, returning a forked path to the parent. Also clarify the height convention: with null = 0, a leaf returns 1, and leftHeight + rightHeight is already an edge count.
Likely follow-ups
- How would you return the actual nodes on the diameter path?
- How would the answer change if the interviewer wanted the number of nodes instead of edges?
- How would you compute the diameter of an N-ary tree?
- What changes if every edge has a different positive weight?
Similar Problems
Key Takeaways
- Diameter is a global best path, while height is the value a parent needs.
- Postorder traversal is natural whenever a node must combine answers from both subtrees.
- A path through a node uses **leftHeight + rightHeight** edges under the **null = 0** height convention.
- Never return a two-branch path upward; parents can extend only one branch.