Diameter of Binary Tree
Easy · Trees · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes.
A path climbs from one node up to a turning point and back down to the other, never using a node twice. The longest one does not have to pass through the root — it can sit entirely inside one subtree. Count edges, not nodes: a single node has diameter 0, and two connected nodes have diameter 1.
Trees here are at most 500 levels deep, so a recursive solution is safe.
The node type and two helpers are provided:
Examples
Input: root = [1,2,3,4,5] Output: 3
4 → 2 → 1 → 3 uses 3 edges, and so does 5 → 2 → 1 → 3. No path is longer.
Input: root = [1,2,None,3,4,5,None,None,6] Output: 4
5 → 3 → 2 → 4 → 6 uses 4 edges and never touches the root. Any path through 1 has at most 3.
Constraints
- 1 <= number of nodes <= 10^4
- -100 <= Node.val <= 100
- the tree is at most 500 levels deep (LeetCode allows 10^4; tightened so recursion fits in the browser)
Approaches
- Measure both heights from scratch at every node — time O(n · h), O(n²) worst case, space O(h)
Related problems
Start free on Cariara · Coding problems · System design studio
