543 · Diameter of Binary Tree

The proof problem of Pattern 2. The obvious recursion — return the diameter — is wrong, and it is wrong for a reason worth being able to say out loud. Return the height; record L + R in a field. That split is sub-variant C, and this is where it is introduced.

1 — Why the obvious recursion fails

The diameter is the number of edges on the longest path between any two nodes. It is tempting to write:

int diameter(TreeNode nd) {          // ✗ does not work
    if (nd == null) return 0;
    int L = diameter(nd.left);
    int R = diameter(nd.right);
    return 1 + Math.max(L, R);       // ← meaningless
}

The last line is where it dies. A parent cannot build a path out of its child's diameter, because a diameter is a path that has already turned — it may not touch the child at all, let alone reach up to the parent. To extend a path upward you need a downward-only measurement, and that is the height.

So the recursion returns the composable thing and the non-composable thing is recorded on the side — a field, an array cell, a mutable box. Every sub-variant C problem has this shape:

• Return the best path that starts here and goes down.
• Record the best path that turns here: L + R.

Every node is the turning point of exactly one candidate path, and the true diameter turns somewhere, so taking the maximum over all nodes of "the path that turns here" is exhaustive. That sentence is the correctness proof.

2 — Return one thing, record another

This tree is chosen so the answer does not pass through the root. Watch node 2 set best = 4, and then watch the root fail to beat it — the root's own candidate is only 3, because it has no right subtree to turn into.

Two numbers leave every node and they are almost never equal. At node 2: L + R = 4 goes into best, while 1 + max(L, R) = 3 goes to the parent. Conflating them is the single mistake this problem exists to prevent.

2.1 Edges or nodes — pick one and stay honest

LC 543 counts edges, and the code above returns a height measured in nodes. The arithmetic still works out, and it is worth seeing why rather than trusting it:

Mixing the two units is the standard off-by-one here: a solution that returns -1 for null (edge-counting height) must record L + R + 2, not L + R. Both are correct; only one of them is correct with the base case you actually wrote.

2.2 The rest of sub-variant C

Four problems, one skeleton, four substitutions. 1372 is the useful one to try last because it shows the returned value does not have to be a single number.

3 — Complexity and edge cases

• Time O(n), space O(h). One postorder pass; the recorded maximum costs nothing.
• Single node: diameter 0. L + R = 0, and 0 edges is right — a common expectation mismatch if you assumed a diameter counts nodes.
• A straight line of n nodes: diameter n − 1. Every node records L + 0, and the deepest one wins.
• Diameter not through the root is the case in the visualizer, and the one that a root-only computation gets wrong. Any solution shaped as height(root.left) + height(root.right) fails here.
• Common bug: initialising best inside the recursive method instead of outside it, which resets it on every call. If you dislike the mutable field, return a two-element array or a small record — but then both values travel upward and you must be explicit about which one the parent may use.

4 — Reference implementation

private int best;

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

private int height(TreeNode nd) {
    if (nd == null) return 0;
    int L = height(nd.left);
    int R = height(nd.right);
    best = Math.max(best, L + R);       // record: the path that turns here
    return 1 + Math.max(L, R);       // return: the path that continues up
}

Delete the best line and this is LC 104 exactly. Sub-variant C is sub-variant A plus one recorded side effect.