Diameter of Binary Tree

Easy· DFS· Tree DP

Problem

The diameter of a binary tree is the number of edges on the longest path between any two nodes. The path does not need to pass through the root. Return that length.

Examples

Input: root = [1,2,3,4,5]

Output: 3

The path 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3) has three edges.

Input: root = [1,2]

Output: 1

Constraints

• 1 <= number of nodes <= 10^4
• -100 <= Node.val <= 100

Hints & approach

Hint 1

Any longest path has a highest node where it bends; it goes down the left side and down the right side from there.

Hint 2

The length of the path bending at a node is height(left) + height(right).

Hint 3

Compute heights bottom-up and update a global best at every node in the same pass.

Approachtry the hints first

Write a height function that returns the number of nodes on the longest downward path. Inside it, after computing the left and right heights, update a running maximum with left + right, which is the number of edges of the path that bends at this node. Return 1 + max(left, right) to the parent. One post-order pass handles every candidate bend point.

Time O(n) · Space O(h)

← PreviousInvert Binary Tree Next →Binary Tree Level Order Traversal