EasyTreesAI interview only
Diameter of Binary Tree
Asked atmetaamazongooglemicrosoftbloomberguber
01 · Problem
Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes in the tree. The path does not have to pass through the root.
The tree is given in level-order, with null marking a missing child. A tree with a single node has diameter 0.
02 · Examples
Example 01
1
/ \
2 3
/ \
4 5Input
root = [1,2,3,4,5]
Output
3
The path 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3) uses 3 edges.
Example 02
Input
root = [1,2]
Output
1
The only path, 2 -> 1, has a single edge.
Example 03
1
/
2
/ \
3 4
/ \
5 6Input
root = [1,2,null,3,4,5,null,null,6]
Output
4
The longest path 5 -> 3 -> 2 -> 4 -> 6 has 4 edges and does not touch the root.
03 · Constraints
- 01The number of nodes in the tree is in the range [1, 100].
- 02-100 <= Node.val <= 100
- 03Path length is counted in edges, not nodes, and the path does not need to pass through the root.
- 04The tree height is at most 100, and the tree may be fully skewed.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(h)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.