Diameter of Binary Tree

Medium

Longest path through any node

In simple words

The longest path is the tallest-left plus tallest-right heights meeting at some node.

The idea

The longest path between two nodes passes through some node, using its left height plus right height. Compute heights bottom-up and track the best left+right seen.

←→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.