Visualize

Pattern visualizer

Diameter of Binary Tree

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

Post-order depth with a side-channel maximum

time O(n)space O(h)step 1 / 11
8
6
4
2
5
7
9
1
3

Call stack

depth(1)
line 8

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.

Pseudocode
1best <- 0
2FUNCTION depth(node):
3  IF node = null: RETURN 0
4  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

Where to practice Binary Trees

Practice Binary Trees problemsAll Binary Trees problemsBack to roadmap