Diameter of a binary tree
Coding problemMediumAsked in: Amazon, Microsoft, NPCI, OYO
Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes. The path does not have to pass through the root.
Trees are written in level order, with null for a missing child. An empty tree and a single node both have diameter 0.
Examples
Example 1
Input: root = [1,2,3,4,5]
Output: 3
The path 4, 2, 1, 3 (or 5, 2, 1, 3) has 3 edges.
Example 2
Input: root = [1,2]
Output: 1
Example 3
Input: root = [1,2,null,3,4,5,null,null,6]
Output: 4
The longest path 5, 3, 2, 4, 6 does not pass through the root.
Constraints
- The tree has between 0 and 100,000 nodes
- Each value is a 32-bit integer
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.