Diameter of Binary Tree
You get the root of a binary tree. The diameter is the length of the longest path between any two nodes in the tree. The path may or may not pass through the root. The length of a path is the number of edges (steps between neighboring nodes) on it.
Return the diameter. A tree with a single node has diameter 0. The tree is written in level order, with null for a missing child.
Examples
Input root = [1, 2, 3, 4, 5]
Output 3
The path 4, 2, 1, 3 has 3 edges.
Input root = [1, 2]
Output 1
Input root = [1]
Output 0
Constraints
- 1 <= number of nodes <= 500
- -100 <= node value <= 100
Stuck? Take one hint at a time
Common mistakes
- Returning left + right as the height, which is the path through the node, not the height of the node for its parent.
- Assuming the longest path always passes through the root, which fails for a tall subtree with a small root.
- Counting nodes instead of edges, so every answer is one larger.
- Using a global variable without resetting it between calls, so the second test inherits the first answer.
Questions an interviewer may ask next
- Return the path itself, not only its length. (Record the node where the best path turns.)
- Find the maximum path sum between any two nodes, where nodes have values. (Binary Tree Maximum Path Sum.)
- Find the diameter of an N-ary tree. (Take the two largest child heights at each node.)
- The tree could have a million nodes and be very deep. How do you avoid a deep recursion? (An iterative post order walk.)
root
[1,2,3,4,5]
Expected output
3
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.