Diameter of Binary Tree (LeetCode 543)

The problem

You get the root of a binary tree. Return its diameter: the number of edges on the longest path between any two nodes. The path doesn’t have to pass through the root.

Input:  [1, 2, 3, 4, 5]

          1
         / \
        2   3
       / \
      4   5

Output: 3

The longest path is 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3), which has 3 edges.

How to think about it

Start with brute force. Every path has a highest node, where it turns from going up to going down. For each node, compute the depth of its left subtree and its right subtree (each an O(n) call) and add them. Doing an O(n) depth calculation at each of n nodes is O(n²) on a skewed tree.

The key insight: you’re already computing those depths. A single post-order DFS that returns each node’s depth gives you l and r at every node for free. The longest path that turns at this node has l + r edges. So while returning depth upward, record l + r in a running best.

Why two different values? The parent needs this node’s depth (one branch, since a path can’t fork), but the answer needs the bend through this node (both branches). The function returns one and updates the other. This “return X, track Y” split is the lesson’s most reusable idea, and it comes back in Maximum Path Sum.

Which pattern is this? Tree DFS with a global. The tell is “longest path between any two nodes”, where the best path may bend at any node, not only the root.

Approach

1. Keep best = 0 outside the recursion.
2. depth(node) returns 0 for an empty node.
3. Otherwise get l = depth(left) and r = depth(right).
4. Update best = max(best, l + r): the path bending here.
5. Return 1 + max(l, r): the longest single branch the parent can extend.
6. Call depth(root) and return best.

Solution

def diameter(root):
    best = 0
    def depth(node):
        nonlocal best
        if not node: return 0
        l = depth(node.left); r = depth(node.right)
        best = max(best, l + r)                              # path that bends at this node
        return 1 + max(l, r)                                 # parent can only extend one branch
    depth(root); return best
# diameter(tree[1,2,3,4,5]) -> 3

Dry run

On the example, in the order nodes finish:

The best bend is at the root, giving 3.

Complexity

• Time: O(n). One post-order pass; each node does O(1) work after its children return.
• Space: O(h). The recursion stack goes as deep as the tree height: O(log n) balanced, O(n) skewed.

Edge cases and pitfalls

• Single node has diameter 0 (no edges). An empty tree also returns 0.
• The best path may not touch the root. If one subtree is long and bushy and the other side is tiny, the bend is deep inside. Returning l + r at the root only is the classic wrong answer.
• Edges vs nodes. l + r counts edges because each depth counts nodes below the bend. If a question wants nodes, add 1.
• Don’t return l + r upward. A parent can’t use both branches of a child, so it must receive 1 + max(l, r).

Related problems

• Binary Tree Maximum Path Sum (LeetCode 124): the same “return a branch, track the bend” idea with values.
• Maximum Depth of Binary Tree (LeetCode 104): the depth function this solution is built on.
• Lowest Common Ancestor of a Binary Tree (LeetCode 236): another post-order DFS that decides at the bend point.