Diameter of Binary Tree

1. Problem & Core Objective

The diameter is the length of the longest path between any two nodes, measured in edges. The path need not pass through the root.

      1
     / \
    2   3        →  3   (the path 4 → 2 → 1 → 3, which is 3 edges)
   / \
  4   5

Constraints: 1 <= nodes <= 10^4 · -100 <= Node.val <= 100

What's actually being tested: the return-versus-record split. The quantity you want (the longest path through a node) is not the quantity the parent can use (the longest path down from a node). Recognising that these are different, and handling both in one traversal, is the single most transferable idea in this section — question 14 is the same pattern with arithmetic instead of counting.

2. First-Principles Thought Process

Anchor the path at its highest node

Any path in a tree has a unique topmost node. Anchoring on that node, the path is:

the longest downward path into the left subtree + the longest downward path into the right subtree

So if I can compute, for every node, the longest path going down from it, I can evaluate every candidate path by summing the two sides — and take the maximum over all nodes.

The crucial asymmetry

Here's where it gets interesting. Consider what a parent can do with a child's result.

A path that goes down-left, up through the node, and down-right cannot be extended upward. It already used both of the node's branches; there is no way out to the parent.

So the parent can only use a path that comes up from one side.

Two different quantities:

The function returns the height and records the diameter as a side effect.

Why this isn't obvious

The instinct is that a recursive function should return the thing you want. Here it can't — the answer isn't composable upward. The moment you accept that the return value and the answer are different things, the problem collapses to six lines.

Every "hard" tree problem in this section is this same realisation.

Units: edges, not nodes

The diameter counts edges. With height(null) = 0 and height(leaf) = 1, the sum leftHeight + rightHeight at a node counts exactly the edges on the through-path — one edge per level on each side. A single node gives 0 + 0 = 0, which is right: a one-node tree has no edges.

3. Solution Paths

Approach 1 — Compute the height at every node independently (brute force)

public int diameterOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int through = height(root.left) + height(root.right);
    int left    = diameterOfBinaryTree(root.left);
    int right   = diameterOfBinaryTree(root.right);
    return Math.max(through, Math.max(left, right));
}

private int height(TreeNode n) {
    if (n == null) return 0;
    return 1 + Math.max(height(n.left), height(n.right));
}

For each node, measure both sides and take the best over all nodes.

• Time O(n²) worst case, O(n log n) balanced · Space O(h)

Counter-questions on this approach

⭐ "Where does the O(n²) come from? Each function looks linear."

height is linear, but it's called from every node, and each call re-walks that node's entire subtree.

On a degenerate tree — a chain of n nodes — the root's height call walks n nodes, its child's walks n−1, and so on: n + (n−1) + … + 1 = O(n²). At n = 10^4 that's 10^8 operations.

On a balanced tree, each of the log n levels does O(n) total height work, giving O(n log n) — better, but still redundant.

⭐ "What exactly is being recomputed?"

Heights. When the root asks for height(left), that call computes the height of every node in the left subtree — and then throws all of it away, keeping one number. Moments later, the recursion on root.left computes those very same heights again.

That's the signal for the fix: I'm already computing everything I need during a single traversal; I just need to capture it on the way back up instead of discarding it.

"Is this ever acceptable?"

If the tree were guaranteed small and shallow, it's readable and obviously correct. But the single-pass version is barely longer, so there's no real trade here.

Approach 2 — One traversal, returning height and recording diameter (optimal)

private int best = 0;

public int diameterOfBinaryTree(TreeNode root) {
    best = 0;
    height(root);
    return best;
}

private int height(TreeNode n) {
    if (n == null) return 0;
    int L = height(n.left);
    int R = height(n.right);

    best = Math.max(best, L + R);        // RECORD: the path THROUGH n (in edges)
    return 1 + Math.max(L, R);           // RETURN: the longest path DOWN from n
}

Trace — [1,2,3,4,5]:

Answer 3 ✓ — the path 4 → 2 → 1 → 3.

• Time O(n) — each node visited exactly once · Space O(h) stack

Counter-questions on this approach

⭐ "Why can't the function just return the diameter?"

Because the diameter through a node is not extendable upward. A path that descends into the left subtree, crosses the node, and descends into the right has already consumed both branches — there's no remaining edge to reach the parent.

The parent needs a path it can extend, which means one coming up from a single side. So the return value has to be the height. The diameter is genuinely a different quantity, and the only place to put it is a side effect.

⭐ "Using a mutable field feels like a hack. Is there a cleaner way?"

It's a legitimate concern — the field makes the method non-reentrant and not thread-safe, which is why I reset it at the start. Two cleaner options: return a small record (height, bestSoFar) from the recursion, or pass a single-element int[] as an accumulator.

The record version is the most honest — it makes explicit that the recursion produces two values. I'd write the field version for brevity and mention the trade.

"Why L + R and not L + R + 1?"

Units. L is the number of edges from n down to the deepest node on the left, and likewise R. Walking down the left and up the right crosses exactly L + R edges — the node itself contributes no edge. Adding 1 would be counting nodes instead, and a single-node tree would report 1 instead of 0.

"Could a path not through any node's L + R be longer?"

No. Every path has a unique topmost node, and when the loop reaches that node, L + R is exactly that path's length — or longer, if a deeper branch exists. Since every node is visited, every path's topmost node is considered, so no path is missed.

"What about stack depth at n = 10^4?"

A degenerate tree gives 10,000 frames, which Java typically survives but not comfortably. An explicit stack with postorder traversal would be the fix, at the cost of considerably more code.

Comparison

4. Why the Optimal Wins

The brute force computes every height many times. The optimal computes each exactly once and captures the by-product on the way back up. O(n²) → O(n), with the same traversal and roughly the same amount of code.

The deeper win is conceptual. Once you accept that the value a recursion returns need not be the value you want, a whole family of problems opens up:

The framing worth keeping:

When the answer at a node cannot be extended to its parent, return what the parent CAN use and record the answer as a side effect.

5. Java Prerequisites

The return-vs-record skeleton

private int best;

private int dfs(TreeNode n) {
    if (n == null) return 0;
    int L = dfs(n.left), R = dfs(n.right);
    best = Math.max(best, combineAcross(L, R));   // record — not returned
    return combineUpward(L, R);                   // return — what the parent uses
}

Reset instance state at the start of the public method — otherwise a second call sees the first call's best.

Avoiding the mutable field — either is fine:

record Result(int height, int best) {}      // return both explicitly
int[] best = new int[1];                    // a one-element accumulator

Postorder is forced here. Both L and R must be known before the node's work runs, so the recursion has to complete before the body — unlike question 1, where the order was free.

6. Interview Communication Guide

Clarifying questions: Does the diameter count edges or nodes (edges — a single node is 0; confirm, it's the off-by-one)? Must the path pass through the root (no — that's the point)? Can the tree be a single node (yes, answer 0)?

The pitch

"Every path has a unique topmost node, so I can anchor on that: the longest path through a node is the deepest descent into its left subtree plus the deepest descent into its right. Take the maximum over all nodes and that's the diameter.

The naive version computes the height at every node, but that re-walks each subtree repeatedly — O(n²) on a degenerate tree. The heights are already being computed; they're just being thrown away.

The key realisation is that the thing I want and the thing the parent needs are different quantities. A path that goes down-left, through the node, and down-right has used both branches — it can't be extended up to the parent. So the parent can only use a path coming up one side.

So the recursion returns 1 + max(left, right) — the height, which is extendable — and records left + right into a running maximum, which is the answer but isn't composable upward.

That gives O(n) time, one visit per node, and O(h) stack.

I'd note the mutable field makes it non-reentrant, so I reset it at the start; returning a (height, best) record avoids that if preferred."

Edge cases to volunteer:

Name the last one. A solution that only measures height(left) + height(right) at the root passes many tests and fails exactly there — it's what "the path need not pass through the root" is warning about.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the actual path, not just its length."

Store, alongside each height, the deepest node reached on that side. When you record a new best at a node, remember it as the path's apex plus its two endpoints, then reconstruct by walking down the deepest branch on each side. O(n) time still, but the bookkeeping roughly triples — worth saying that returning a path is materially harder than returning a length.

⭐ "Find the diameter of a general graph rather than a tree."

Very different. For an unweighted tree you can BFS from any node to find the farthest node u, then BFS from u — the farthest node from u is the other end of the diameter. That's O(n) and a nice trick, but it depends on there being no cycles. For a general graph you need all-pairs shortest paths, so O(V·E) with BFS from every node, or Floyd–Warshall at O(V³).

"Weighted edges instead of counting them."

Replace 1 + max(L, R) with max(L + w_left, R + w_right) and record L + w_left + R + w_right. The structure is identical — only the arithmetic changes. Negative weights would additionally require the clamping trick from question 14.

"Diameter of an n-ary tree."

Same idea, but you need the two largest child heights rather than left and right. Track the top two as you loop over children: record top1 + top2, return 1 + top1. It's a clean generalisation and a good test of whether the pattern was understood.

"What if the tree changed and you had to re-query the diameter often?"

Recomputing is O(n) per query. Cache the height at each node and invalidate only along the path from a changed node to the root — O(h) per update. That's the standard augmented-tree technique, and it's why AVL trees store heights in the nodes.

"Avoid recursion entirely."

Postorder with an explicit stack, keeping a map from node to computed height. Same O(n) time, same O(h) memory, but now on the heap where the size is yours to control. That's the answer when the tree could be 10^6 nodes deep.