Faangprep Logo
LoginRegister
Depth-First Search
Easy

Diameter of Binary Tree

Find the length of the longest path between any two nodes in a tree.
10 min read
Solve on LeetCode
Examples
Input:root = [1,2,3,4,5]
Output:3
Explain:

Path is [4,2,1,3] or [5,2,1,3], length 3 (3 edges).

Problem Understanding

The diameter (or width) of a tree is the number of edges on the longest path between any two nodes.

Crucially, the path does NOT need to pass through the root. It could be entirely contained within the left or right subtree.

Algorithm Strategy

We use Post-Order DFS.

At any specific node, the longest path that passes through this node is LeftHeight + RightHeight.

However, the global maximum diameter could be found at a child node (not passing through current).

So:

  1. Return Value: Max height (depth) of the subtree (max(L, R) + 1).
  2. Side Effect: Update global maxDiameter = max(maxDiameter, L + R).
Interactive Visualization
Step 1 / 11
1
curr
2
3
4
5
1
0
2
1
3
2
4
3
5
4

Visiting Node 1. Asking Left and Right children for their Heights...

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep