Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Diameter of a Binary Tree

LeetCode #543Easy
Post-order heights, track the widest split

Given the root of a binary tree, return the length of its diameter: the number of edges on the longest path between any two nodes, which need not pass through the root.

Asked atAmazonMetaGoogle
step 1 / 23
binary tree
4
2
5
1
3
call stack ↓
(returned)
Recursive DFS (post-order height + global max)
▸
1best = 0
2height(node):
3    if node is null: return -1          // base case
4    L = height(node.left)
5    R = height(node.right)
6    best = max(best, (L+1) + (R+1))     // path through node
7    return 1 + max(L, R)                // height for parent
8// answer = best
state
  • goallongest path in edges
  • global best0

line 1The diameter is the longest path — counted in EDGES — between any two nodes. The key insight: that path may NOT pass through the root, but it always bends at SOME node. At each node, the longest path that bends there equals leftHeight + rightHeight. So we run one post-order pass: the helper returns each node's HEIGHT, and along the way we keep a global best of leftH + rightH.