4.14.3 — Diameter of Binary Tree

LeetCode 543 · Easy

The problem

Return the length of the longest path between any two nodes, measured in edges. The path does not have to pass through the root.

     1
   /   \
  2     3      →  3     (the path 4 → 2 → 1 → 3)
 / \
4   5

The pattern

Every path in a tree has a highest point — the node where it turns around. For a path through node X, the best it can be is:

\text{depth of left subtree} + \text{depth of right subtree}

measured in edges. So try every node as the turning point and keep the largest.

That would be O(n^2) if you recomputed the depths at each node. But you can compute the depth of every node in one pass anyway, and the diameter falls out as a side effect of that pass.

The idea that trips people up

Here is the part worth slowing down on, because it is the shape of many hard tree problems:

What the function returns is not what the problem asks for.

The function returns the depth of the subtree, because that is what its parent needs. The diameter is recorded in a variable on the side, updated at every node as the recursion passes through.

The reason for the split: a parent can only use a path that goes through this node and continues upwards, so it can only inherit one side, not both. But the answer to the problem is allowed to turn around here and use both sides. Those are two different numbers, so one is returned and the other is stored.

Once you see this — return what the parent needs, record what the problem wants — a whole family of tree problems becomes routine, including 4.14.14 Binary Tree Maximum Path Sum, which is this exact structure with sums instead of lengths.

The solution

Python

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

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

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

            self.best = max(self.best, left + right)   # path turning here
            return 1 + max(left, right)                # what the parent needs

        depth(root)
        return self.best

TypeScript

function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;

  function depth(node: TreeNode | null): number {
    if (!node) return 0;

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

    best = Math.max(best, left + right);
    return 1 + Math.max(left, right);
  }

  depth(root);
  return best;
}

left + right with no + 1, because the answer is in edges. If the left subtree has depth 2 and the right has depth 1, the path runs 2 edges down one side and 1 down the other, for 3 edges total. Counting nodes instead would need left + right + 1. Check which one the problem wants — this is the most common wrong answer here, and the two differ by exactly one.

1 + max(left, right) is what goes to the parent, because a path continuing upward can only use the deeper of the two sides.

self.best in Python. A plain local variable inside the nested function would be read-only from the inner scope; assigning to it would create a new local. Use an instance attribute, a nonlocal declaration, or a one-element list. JavaScript closures capture by reference, so a plain let works.

Trace

     1
   /   \
  2     3
 / \
4   5

node	left depth	right depth	left+right	best	returns
4	0	0	0	0	1
5	0	0	0	0	1
2	1	1	2	2	2
3	0	0	0	2	1
1	2	1	3	3	3

The answer 3 was recorded at the root, but node 2 also contributed a candidate of 2 along the way. On a tree where the longest path does not pass through the root, one of those intermediate candidates wins instead — which is exactly why the maximum is tracked at every node rather than only at the top.

Complexity

O(n) time — one visit per node. O(h) space for the recursion.

Where this goes next

The same two-value structure — return one thing, record another — covers a family:

• Binary Tree Maximum Path Sum — return the best downward sum, record the best turning sum. 4.14.14.
• Longest Univalue Path — same, restricted to edges joining equal values.
• Longest ZigZag Path — return two values, one per direction.
• Balanced Binary Tree — return the depth, record whether balance was ever violated. 4.14.4.

What the interviewer will push on

"Why does the function return depth instead of diameter?" A parent can only extend a path through one side, so it needs the depth. The diameter uses both sides and cannot continue upwards, so it is recorded separately.

"Edges or nodes?" Edges here. Say which you are counting before writing the formula.

"Does the path have to go through the root?" No — which is precisely why every node is tried as a turning point.

One thing to volunteer: name the pattern out loud. "Return what the parent needs; record what the question wants." That sentence carries you through the two hard tree problems later in this chapter.

Next: 4.14.4 Balanced Binary Tree — the same structure, using a sentinel return value to stop early.