Diameter of Binary Tree

Difficulty: Medium

Problem

Given the root of a binary tree, return the diameter — the LENGTH of the longest path between any two nodes, measured in EDGES. The path may or may not pass through the root.

Example

Input: root = [1,2,3,4,5]
Output: 3
Explanation: The longest path is 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3), which crosses 3 edges. Note 4 → 2 → 5 is only 2 edges.

Brute-force approach

There is no separate brute-force phase — but note the naive approach (call height() at every node) costs O(n²). The lesson's one-pass version is the optimal form of the same idea.

Optimal approach

Key insight: Each call RETURNS the height its parent needs, while RECORDING a shared best-diameter as a side quest. Return one thing, record another — the pattern that unlocks hard tree problems.

One postorder traversal computes each node's height AND lets each node try itself as the path's bend (leftHeight + rightHeight), tracking the best bend seen anywhere.

Steps

  1. Track a global best, starting at 0
  2. Recursively compute each node's height (postorder: children first)
  3. At every node, try bend = leftHeight + rightHeight and update best
  4. Return 1 + max(leftHeight, rightHeight) — the straight chain the parent can extend
  5. After the traversal, best is the diameter

Time complexity: O(n) · Space complexity: O(h) where h = height of tree