Diameter of Binary Tree
Post-order depth with a side-channel maximum
Every path has a unique highest node where it turns, and its length there is the depth of the left branch plus the depth of the right branch. One post-order pass computes each node's depth for its parent while recording the best turn seen anywhere — the longest path need not touch the root.
Details
Animated on: Return the diameter of the binary tree [1,2,3,4,5,null,null,6,null,null,7,8,null,null,9] — the number of edges on the longest path between any two nodes.
Problem:Diameter of Binary TreeEasy
Pattern:Tree DFS
Post-order depth with a side-channel maximum
step 1 / 11
Call stack
Call depth(1) at the root. The diameter is the longest path between any two nodes; every path has one highest node where it turns, and its length there is left depth + right depth. So we recurse to the leaves first — no node can answer until its children have.
1best <- 02FUNCTION depth(node):3 IF node = null: RETURN 04 left <- depth(node.left)5 right <- depth(node.right)6 best <- MAX(best, left + right)7 RETURN 1 + MAX(left, right)8depth(root)9RETURN best
← / → step · space play · Home restart
Every step in words
Show all 11 steps
- Call depth(1) at the root. The diameter is the longest path between any two nodes; every path has one highest node where it turns, and its length there is left depth + right depth. So we recurse to the leaves first — no node can answer until its children have.
- Leaf 8: both children are null and return 0, so the longest path turning here has 0 + 0 = 0 edges. It reports depth 1 to its parent (4 frames still waiting).
- Node 6 now has both answers: left depth 1, right depth 0. The longest path that TURNS at 6 is 1 + 0 = 1 edges. That beats the best so far (0), so best becomes 1. It returns 1 + MAX(1, 0) = 2 to its parent, since a parent can only extend one branch.
- Node 4 now has both answers: left depth 2, right depth 0. The longest path that TURNS at 4 is 2 + 0 = 2 edges. That beats the best so far (1), so best becomes 2. It returns 1 + MAX(2, 0) = 3 to its parent, since a parent can only extend one branch.
- Leaf 9: both children are null and return 0, so the longest path turning here has 0 + 0 = 0 edges. It reports depth 1 to its parent (4 frames still waiting).
- Node 7 now has both answers: left depth 0, right depth 1. The longest path that TURNS at 7 is 0 + 1 = 1 edges. Best stays 2. It returns 1 + MAX(0, 1) = 2 to its parent, since a parent can only extend one branch.
- Node 5 now has both answers: left depth 0, right depth 2. The longest path that TURNS at 5 is 0 + 2 = 2 edges. Best stays 2. It returns 1 + MAX(0, 2) = 3 to its parent, since a parent can only extend one branch.
- Node 2 now has both answers: left depth 3, right depth 3. The longest path that TURNS at 2 is 3 + 3 = 6 edges. That beats the best so far (2), so best becomes 6. It returns 1 + MAX(3, 3) = 4 to its parent, since a parent can only extend one branch.
- Leaf 3: both children are null and return 0, so the longest path turning here has 0 + 0 = 0 edges. It reports depth 1 to its parent (1 frame still waiting).
- Node 1 now has both answers: left depth 4, right depth 1. The longest path that TURNS at 1 is 4 + 1 = 5 edges. Best stays 6. It returns 1 + MAX(4, 1) = 5 to its parent, since a parent can only extend one branch.
- Every node has returned. The best turn was 6 edges, found at node 2, not at the root — the root's own turn is only 4 + 1 = 5. That is why the maximum is tracked as a side effect while depths bubble up, instead of read off the root's return value.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.