LeetCode 543 – Diameter of Binary Tree

Diameter of Binary Tree is tagged Easy, and the pattern it teaches carries most of the Hard tree problems. The difficulty is that the recursion has to do two things at once: return one quantity to its caller while updating a different one globally. Once you have written that shape, Binary Tree Maximum Path Sum stops being scary.

The problem

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
     / \
    4   5

The longest path is 4 - 2 - 1 - 3 (or 5 - 2 - 1 - 3): four nodes, three edges.

"May or may not pass through the root" is the phrase to notice. A tree whose left subtree is a long chain and whose right subtree is empty has its diameter buried entirely on one side, nowhere near the root — so anything computed only at the root is wrong.

The two quantities

Any path in a tree has a single highest node — the topmost point it reaches. At that node the path is exactly the deepest reach into the left subtree, plus the deepest reach into the right. So if you visit every node and, at each one, consider the path that turns around there, you consider every possible path exactly once.

That gives two different numbers per node, and conflating them is the classic mistake:

Depth — how far down you can go from this node. This is what the recursion returns, because the parent needs it. A path continuing up through the parent can only use one side, so it is max(left, right) + 1.
Diameter through this node — left + right. This is what gets recorded, because such a path turns around here and cannot be extended upwards.

You cannot return both up the same channel, so the diameter goes into a variable that outlives the recursion while the depth flows back normally. That split is the whole pattern.

Edges, not nodes

The problem measures edges, and the code returns node counts — yet left + right is already correct, which looks like luck. It is not. If the left reach is L nodes and the right is R nodes, the through-path has L + R + 1 nodes counting this one, and a path with L + R + 1 nodes has L + R edges. The + 1 cancels.

Check it against a leaf: both children return 0, so the recorded diameter is 0 — a single node is a path of no edges. Correct. Derive this rather than trusting it; an off-by-one in a tree problem is very hard to spot by staring.

Java

class Solution {
    private int best;

    public int diameterOfBinaryTree(TreeNode root) {
        best = 0;            // reset, so calling twice on one instance is safe
        depth(root);
        return best;
    }

    /** Returns the depth below this node, recording the best diameter on the way. */
    private int depth(TreeNode node) {
        if (node == null) return 0;

        int left = depth(node.left);
        int right = depth(node.right);

        // A path turning around HERE. It cannot be extended upwards, so record it now.
        best = Math.max(best, left + right);

        // What the parent needs: a path going DOWN can only use one side.
        return Math.max(left, right) + 1;
    }
}

Note the explicit best = 0. Holding state in a field is what makes the two-quantity trick readable, but it also means a second call on the same object would otherwise inherit the first call's answer — the exact bug the Longest Palindromic Substring solution has to avoid. Resetting at the public entry point costs one line and makes the class safe to reuse. If you would rather have no field at all, pass an int[1] holder or return a two-element array — same idea, more noise.

Python

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        best = 0

        def depth(node) -> int:
            nonlocal best
            if not node:
                return 0

            left = depth(node.left)
            right = depth(node.right)

            best = max(best, left + right)      # path turning around here, in edges
            return max(left, right) + 1         # what the parent needs

        depth(root)
        return best

nonlocal is what makes the closure write to the enclosing best rather than shadowing it with a new local. Without it the assignment silently creates a fresh variable per call and the function returns 0 for every input — a failure that produces no error at all.

Complexity

O(n) time: every node is visited exactly once, and the work at each is two comparisons. Space is O(h) for the recursion stack, where h is the height — O(log n) on a balanced tree and O(n) on a degenerate one that is really a linked list. Quote the height, not log n; the problem says nothing about balance.

The naive alternative computes depth at every node from scratch, making it O(n²) — or O(n log n) if balanced. The single-pass version avoids that by having each node reuse the depths its children already computed, which is the same compute-on-the-way-back-up move that turns many tree recursions linear.

The family

Binary Tree Maximum Path Sum (124) — identical skeleton, Hard rather than Easy. Return the best downward sum, record left + right + node.val, and clamp negative child contributions to 0 since you may decline a subtree. If you can write 543 cold, 124 is that one extra rule.
Maximum Depth of Binary Tree (104) — just the return value, with nothing recorded. Worth writing first if the pattern is new.
Longest Univalue Path (687) — same again, but a child only contributes when its value matches the parent's.
Balanced Binary Tree (110) — return the depth and record a boolean instead of a maximum.

What the interviewer is checking

That you separate "what I return" from "what I record", and can say why both are needed.
That you do not assume the path goes through the root.
That the answer is in edges, and that you derived left + right rather than guessing.
That it is one pass, not depth recomputed at every node.
null root, a single node, and a completely one-sided tree.
That you state the space as O(h) and note it is O(n) when degenerate.