Skip to main content
Back to ChallengesDiameter of Binary TreeMedium 25 min

Diameter of Binary Tree

Given the root of a binary tree, return the **diameter** — the length of the longest path between any two nodes.

The path may or may not pass through the root. The length is measured in **number of edges**.

Examples

Input: root = [1,2,3,4,5]
Output: 3
Path [4,2,1,3] or [5,2,1,3], length 3.
Input: root = [1,2]
Output: 1
Single edge between 1 and 2.

Constraints

  • • Number of nodes in [1, 10^4]
  • • -100 <= Node.val <= 100

Complexity Analysis

Time
O(n)
Space
O(h)

Test Cases

#1 Standard case
Input: [1,2,3,4,5]
Expected: 3
#2 Two nodes
Input: [1,2]
Expected: 1
#3 Single node
Input: [1]
Expected: 0
#4 Left-skewed
Input: [1,2,null,3,null,4]
Expected: 3
JavaScript
Output
Click "Run Code" to see output here...