Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The diameter is the longest path (counted in edges) between any two nodes — it need not pass through the root. Run one post-order DFS where each node returns its height (1 + max(leftHeight, rightHeight)). At every node, the longest path bending there is leftHeight + rightHeight edges; update a global maximum with that. Return the height upward, record the split globally. O(n) time, O(h) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you separate two values in one DFS — the height you return upward versus the bending path (left + right) you record globally — and whether you count edges, not nodes.
Where candidates slip
Returning `1 + L + R` upward (mixing height with the bending path), or counting nodes so every answer is off by one, or recomputing height per node and shipping an O(n²) solution.
How to stand out
State the brute force (height-per-node, O(n²)) first, then collapse it into one post-order pass. Name the 'return height, record split' pattern and tie it to Maximum Path Sum.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Return 1 + max(L, R) to the parent; record L + R (the bending path in edges) as a global candidate.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Height Computed at Every Node
1Hint 1Explore hintHide hint
Every path has a single highest node where it bends. Fix that node: what is the longest path that bends exactly there?
2Hint 2Explore hintHide hint
The longest path bending at node X is height(X.left) + height(X.right) edges. Take the maximum of that over all nodes.
3Hint 3Explore hintHide hint
Computing height(X) is itself a recursion over a subtree. Calling it for every node independently repeats work — that is the O(n²).
A · Core idea
Begin from the observation that every path peaks at exactly one node — the unique highest point where it can branch into both subtrees. So the diameter is the maximum, over all nodes, of 'longest path that bends at this node'.
The path that bends at a node. Let height(x) be the number of edges on the longest downward chain from x to any leaf, with an empty subtree having height 0. The longest path bending at node p uses the deepest chain on each side: height(p.left) + height(p.right) edges. The diameter is the maximum of this quantity across all nodes.
Why it counts edges cleanly. Each height is an edge count, and joining a left chain and a right chain at p simply adds the two edge counts — p itself contributes no extra edge because it is the meeting point. A leaf has 0 + 0 = 0, which is correct.
Why it is quadratic. Computing height(x) walks the whole subtree under x. If we call it once per node as a separate pass, the same heights are recomputed again and again — n nodes × O(n) per height = O(n²). For n = 10⁴ that is up to ~10⁸ operations, slow and wasteful.
Why mention it. It nails the framing — 'paths bend at a node, combine two downward arms' — that the optimal reuses. The jump to O(n) is just: compute each height once and fold the bend check into the same traversal.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,3,4,5]bend 4
height(null) + height(null) = 0 + 0
candidate = 03C · Code with teaching comments
Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
Realizing every path has a single bend point turns a scary 'all pairs of nodes' search into 'for each node, the longest path that bends here'. The only inefficiency is recomputing heights; doing each height once in a post-order pass is the whole optimization.
ComplexityO(n²) time, O(h) space — For each of the n nodes we compute the height of its two subtrees, each an O(n) DFS in the worst case → O(n²) time. Recursion depth is bounded by the tree height → O(h) space.
E · Edge cases and pitfalls3Recomputing height() for every node — the source of the quadratic cost.Explore edge casesHide edge cases
Pitfalls
- Recomputing height() for every node — the source of the quadratic cost.
- Counting nodes instead of edges — every answer comes out one too large.
- Forgetting the bend uses BOTH arms while height() uses only one.
Approach 2 of 2 · Optimal
Single Post-Order DFS — Height Up, Split Recorded (Optimal)
1Hint 1Explore hintHide hint
In the brute force, height(x) was recomputed everywhere. What if each node computed its height exactly once and handed it up?
2Hint 2Explore hintHide hint
Have the recursion return the height (one branch). At the same node, while you hold both children's heights, compute the bending path (left + right edges) and update a global best.
3Hint 3Explore hintHide hint
Return 1 + max(L, R) upward, but record L + R as the global diameter candidate. One traversal, no second pass.
A · Core idea
Fold the whole computation into one post-order DFS. The trick is to keep two related quantities strictly apart.
Quantity 1 — the height returned upward. When the recursion finishes a node, it returns the length of the longest downward chain from this node: 1 + max(L, R), where L and R are the children's heights. We return only one branch because the parent will attach this node as a link in a straight chain — a chain cannot pass through both children of a node and still continue upward.
Quantity 2 — the global best (the bend). At the same node we ask: what is the longest path whose highest point is this node? It dips into both children, giving L + R edges. This value is not returned upward (a path cannot both fork here and extend to the parent), but it is a candidate for the overall diameter, so we fold it into a global maximum.
Why these must differ. This is the whole difficulty. If you returned L + R (or 1 + L + R) to the parent, the parent could attach a path that already used both of this node's branches and still extend upward — an impossible shape that revisits the node. Returning only the single best branch keeps every upward extension a legal straight chain, while the global captures the legal bends.
Why post-order. A node cannot compute either quantity until it knows both children's heights, so we must finish the children before the parent — that is post-order (left, right, then node).
Edges versus nodes again. Because height counts edges (empty subtree = 0, leaf = 1 returned but 0 + 0 = 0 recorded), L + R is automatically an edge count. If you instead made height count nodes, you would have to subtract along the way — easier to just count edges from the start.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,3,4,5]Interactive diagram
The winning bend at the root
height(4)4 → 2 → 1 → 3 is 3 edges and bends at node 1; node 5 is an equal-length alternative.
3C · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The pattern is 'return a partial result, record a complete result'. The upward return is deliberately weaker (one branch, the height) than the value scored globally (two branches, the bend) because they answer different questions: 'how deep am I for my parent to extend?' versus 'what is the longest path that peaks at me?'. This exact split powers Binary Tree Maximum Path Sum and Longest Univalue Path.
ComplexityO(n) time, O(h) space — A single post-order visit touches each node once with O(1) work → O(n) time. The only extra memory is the recursion stack, bounded by the tree height → O(h) space.
E · Edge cases and pitfalls6root = [1] — Leaf: left=right=0, bend = 0 → best = 0; returns 1. Counting edges gives the correct 0.Explore edge casesHide edge cases
Edge cases handled
root = [1]Leaf: left=right=0, bend = 0 → best = 0; returns 1. Counting edges gives the correct 0.Straight chain [1,2,null,3,null,4]No bend uses two arms; best ends up the full depth − 0 = number of edges down the chain (3).Deeply skewed tree near 10⁴ nodesRecursion depth equals the chain length; mention an explicit stack if depth could exceed the language limit.
Pitfalls
- Returning left + right (or 1 + left + right) upward — allows an illegal path that forks and still extends.
- Counting nodes instead of edges — every result is one too large.
- Recursing without a depth guard on pathological skewed trees — risk of stack overflow on very deep inputs.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Counting nodes instead of edges
The diameter is defined in edges. If height counts nodes, a single node reports height 1 and a leaf-to-leaf path comes out one too large. Count edges from the start: empty subtree = 0, and the bend is left + right.
Explore the code comparisonHide the code comparison
Counting nodes instead of edges
The diameter is defined in edges. If height counts nodes, a single node reports height 1 and a leaf-to-leaf path comes out one too large. Count edges from the start: empty subtree = 0, and the bend is left + right.
Don't write this
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
# then recording node count along the path and subtracting laterWrite this instead
left = height(node.left)
right = height(node.right)
self.best = max(self.best, left + right) # edges, no off-by-one
return 1 + max(left, right)2Returning the bend sum upward
The value handed to the parent must be a straight downward chain (one child). Returning left + right lets the parent extend a path that already used both of this node's branches — a shape that would revisit the node.
Explore the code comparisonHide the code comparison
Returning the bend sum upward
The value handed to the parent must be a straight downward chain (one child). Returning left + right lets the parent extend a path that already used both of this node's branches — a shape that would revisit the node.
Don't write this
best = Math.max(best, left + right);
return left + right; // illegal: both branches handed upWrite this instead
best = Math.max(best, left + right);
return 1 + Math.max(left, right); // one branch up3Two-pass height recomputation
Calling a separate height() inside a per-node loop recomputes the same subtree heights repeatedly, turning an O(n) problem into O(n²). Fold the height into the same DFS that records the global best.
Explore the code comparisonHide the code comparison
Two-pass height recomputation
Calling a separate height() inside a per-node loop recomputes the same subtree heights repeatedly, turning an O(n) problem into O(n²). Fold the height into the same DFS that records the global best.
Don't write this
def best_bend(node):
bend = height(node.left) + height(node.right) # height re-walks subtree
return max(bend, best_bend(node.left), best_bend(node.right))Write this instead
def height(node):
left = height(node.left)
right = height(node.right)
self.best = max(self.best, left + right)
return 1 + max(left, right)Revise
Carry the pattern into the interview
Pattern to remember
Post-order DFS returning height while a global max records left + right
Code pattern to memorize
self.best = 0
def height(node):
if not node: return 0
L = height(node.left)
R = height(node.right)
self.best = max(self.best, L + R) # path bending here, in EDGES
return 1 + max(L, R) # height returned to parentRules to remember
- 1Diameter is measured in edges, not nodes — a single node has diameter 0, two nodes have diameter 1.
- 2A node returns
1 + max(L, R)(one branch, its height) — the parent extends a single chain. - 3A node updates the global with
L + R(both branches) — the longest path that bends at this node. - 4Use post-order: you cannot compute
LandRuntil both children have reported their heights. - 5Define empty subtree height as 0 so a leaf returns height 1 and its bending path is
0 + 0 = 0edges.
Use this pattern when
- Longest path / distance between two nodes in a tree where the path can bend at one node
- When the value you return to a parent differs from the value you record globally
- Any tree metric that combines two child results at a node but extends only one upward
- Width / depth style questions where each node contributes a 'through me' candidate
Choose another pattern when
- Path must be root-to-leaf only → simple top-down depth, no global split needed
- You need the actual node sequence, not the length → reconstruct, more bookkeeping
- Graph with cycles, not a tree → BFS two-pass (farthest node twice) instead of DFS
- Weighted edges → carry edge weights instead of counting 1 per edge
Interview takeaway
Diameter is the textbook case of 'return partial, record full': the height handed upward uses one child so a parent can keep a straight chain, while the global captures the bend through both children. The same engine solves Binary Tree Maximum Path Sum and Longest Univalue Path.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternPost-order DFS that returns a partial (single-branch height) value while recording a complete (both-branch) value globally. Reach for it whenever a tree path can bend at a node but the value handed to a parent must stay a straight chain. Same engine as Binary Tree Maximum Path Sum and Longest Univalue Path.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Binary Tree Maximum Path SumSame shape with values: return val + max(0, gain) up, record val + leftGain + rightGain globally.
- Longest Univalue PathComing soonReturn the longest same-value arm upward; record left arm + right arm (same value) globally.
- Tree Diameter (N-ary / Graph)Coming soonFor a general tree given as edges, either the same DFS over an adjacency list, or BFS from the farthest node twice.
- Maximum Depth of Binary TreeThe height subroutine on its own — the building block this problem extends.