Diameter of a Binary Tree

Medium

Return the height, track the best bend

Problem

Return the length of the longest path between any two nodes in a binary tree (in edges).

In simple words

At each node, the best path through it is left height + right height; keep the largest.

The idea

The longest path either bends at some node — where it is leftHeight + rightHeight — or lies entirely in a subtree. Returning the height while updating a running maximum captures both in one O(n) pass.

The trick

The path bending at a node spans leftHeight + rightHeight; the diameter is the largest such span over every node.
Measure it in the same post-order pass that computes each node's height — no extra traversal needed.

←→stepspaceplay

1/8

Optimal

timeO(n)spaceO(h)

Best = max(left+right).

1let best = 0;2function height(node) {3  if (!node) return 0;4  const l = height(node.left), r = height(node.right);5  best = Math.max(best, l + r);6  return 1 + Math.max(l, r);7}

Input

nodes: 6, 5 edges

Memory

l+r: —

Output

best: —
diameter: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [1,2,3,4,5]
Output:: 3
Explanation:: The longest path (4-2-1-3 or 5-2-1-3) has 3 edges.

Example 2

Input:: tree = [1,2]
Output:: 1
Explanation:: Just one edge between the two nodes.

Example 3

Input:: tree = [1]
Output:: 0
Explanation:: A lone node has no edges.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.