Diameter of Binary Tree

Given the root of a binary tree, return the length of its diameter — the number of edges on the longest path between any two nodes. This path may or may not pass through the root.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

For any node, the longest path bending at it is leftHeight + rightHeight edges.

The diameter is the maximum of that quantity over all nodes.

Compute height once bottom-up; return 1+max(L,R) upward but record L+R globally.

Common doubts

A parent can extend only one downward branch (so it wants max), but the diameter can bend and use both branches at this node (so the record uses the sum).

Edges — a path visiting k nodes has k−1 edges, so a single node has diameter 0.

No — it may lie entirely within a subtree, which is why every node is considered.

Interview follow-ups

· What an interviewer asks next.

Identical shape: return the best single downward branch, record the best bending path (there, a sum of values instead of a count of edges).

Track the node that achieved the maximum and its two deepest branches, then reconstruct by walking down both sides.

Fun facts

Diameter and maximum-path-sum are the same algorithm with a different quantity being combined at each node.
The 'return one branch, record both' idea generalizes to many tree DPs where a global answer bends at a node.

Asked at

AmazonFacebookGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 2, 3, 4, 5]
Output: 3
The longest path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3), which has 3 edges.

Example 2

Input: root = [1, 2]
Output: 1
The path 1 -> 2 has a single edge.

Constraints

- The number of nodes is in the range [1, 10^4] - -100 <= Node.val <= 100

The longest path in a tree, for any node it passes through the top of, is leftHeight + rightHeight edges. So the diameter is the maximum of that quantity over all nodes. The trick — shared with maximum-path-sum — is that the function returns the longest downward path (so a parent can extend it), while recording the longest path that bends at the node.

Prerequisites

Before you start

· Concepts used directly in the solution.

Tree height. Longest downward path from a node, in edges.

Return vs record. Return one child's path upward; record both children's combined path globally.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Edges or nodes?”

Edges — a path of k nodes has k−1 edges; a single node has diameter 0.

“Must the path pass through the root?”

No — it can lie entirely in one subtree.

The ideal opening — say it like this

For any node, the longest path bending at it is the left subtree's height plus the right subtree's height, in edges.

So I compute heights bottom-up and keep a running maximum of left-plus-right, while each call returns one plus the taller child so its parent can extend it.

Understand the problem

Worked example — tree [1, 2, 3, 4, 5]

        1
       / \
      2   3
     / \
    4   5
depth(4)=depth(5)=0 -> depth(2): L=1,R=1 -> record 1+1=2 edges (path 4-2-5)
node 1: L=depth(2)=2, R=depth(3)=1 -> record 2+1=3 edges (path 4-2-1-3)
answer: 3

Key observations

1Aha

Diameter through a node = leftHeight + rightHeight

Measured in edges, the bending path at a node is exactly the sum of its two subtree heights.

2Aha

Return one child, record both

Upward you can only extend a single branch, so return 1 + max(L, R); the both-branches sum only ever lives in the global answer.

3Aha

One pass is enough

Folding the record step into the height computation gives O(n), versus O(n²) if you recompute height at every node.

Brute force vs optimal

	Recompute heights per node	Single-pass depth + record
Idea	At each node, add its two subtree heights	One postorder pass; record L+R, return 1+max(L,R)
Time	O(n^2)	O(n)
Space	O(height)	O(height)

The single-pass version reuses each height. Full code is in the Approaches selector below.

Summary

Key takeaway

Diameter = max over nodes of (leftHeight + rightHeight) edges. In one postorder pass, record L+R into a global maximum and return 1+max(L,R) upward. O(n) time, O(height) space.

depth(node):
    if node is null: return 0
    L = depth(node.left); R = depth(node.right)
    best = max(best, L + R)
    return 1 + max(L, R)