Browse Curriculum
FAANGPrep Sprint
Easy
Diameter of Binary Tree
Find the length of the longest path between any two nodes in a tree.
10 min read
Solve on LeetCodeExamples
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:
- Return Value: Max height (depth) of the subtree (
max(L, R) + 1). - Side Effect: Update global
maxDiameter = max(maxDiameter, L + R).
Interactive Visualization
Step 1 / 1
Empty Heap
Initializing...
1x
Visualize heights bubbling up, and the diameter updating whenever L+R is larger than before.
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.