Diameter of Binary Tree

Difficulty: Medium

Problem

For the binary tree rooted at root, find its diameter, meaning the number of EDGES on the longest path joining any two nodes. That path is allowed to bypass the root.

Example

Input: root = [7,3,9,1,4,null,null,null,null,null,2]
Output: 4
Explanation: The longest path is 2 → 4 → 3 → 7 → 9, which has 4 edges. The path 2 → 4 → 3 → 1 is shorter at 3 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

Pseudocode

function diameterOfBinaryTree(root):
    best = ____
    
    function height(node):
        if node is null:
            return ____
        L = height(node.left)
        R = height(node.right)
        
        best = max(best, ____)      // record the bend
        return ____                 // return to parent
    
    height(root)
    return best

Hints

  • best starts at the diameter of a single node, how many edges is that?
  • The bend at this node joins the two child chains: which two values add up?
  • The parent can only extend a STRAIGHT chain: yourself plus the taller child
  • Careful: the record line and the return line use DIFFERENT formulas. That's the whole lesson!

Complexity questions

What is the time complexity of the one-pass solution?

O(n): each node computes its heights exactly once. One postorder traversal: every node does O(1) work (a max, an add, a compare) on top of its two recursive calls. Total O(n).

What does the naive approach, a separate height() call at every node, cost?

O(n²) in the worst case, because heights get recomputed for overlapping subtrees. height() itself is O(subtree size). Calling it at each of n nodes re-walks overlapping subtrees again and again: up to O(n²) on skewed trees. The one-pass version computes each height once.

What is the space complexity?

O(h): the recursion stack. Only the recursion stack: O(log n) for balanced trees, O(n) for skewed ones. best is a single number.

Why can't height() return L + R to its parent?

A bent path can't be extended upward: the parent needs a straight chain, and returning the bend would build impossible double-bent paths. A path may bend at most once (at its highest node). If a node handed its bend to the parent, the parent's own bend would create a path that turns twice, not a valid path. Straight chains go up; bends stay local as recorded candidates.

Check your understanding of Diameter of Binary Tree

The diameter is measured in what units?

The number of EDGES between the two end nodes. Edges, not nodes. The path 4 → 2 → 1 → 3 touches 4 nodes but crosses 3 edges, its length is 3. Off-by-one here is the most common wrong answer on this problem.

Must the longest path pass through the root?

No: it can live entirely inside one subtree. Picture a tiny right subtree and a huge, deep left subtree: the longest path may connect two leaves deep inside the left side without ever touching the root. That's why we must consider EVERY node as a potential 'peak' of the path.

Every path has a highest node where it 'bends'. Standing at that bend node, the path's length equals what?

leftHeight + rightHeight: the two downward chains joined at the bend. A path climbs up one side to the bend and back down the other. With height counted in nodes-per-chain, left chain + right chain gives exactly the edge count. Check at root 1 of [1,2,3,4,5]: left height 2 (chain 2→4) + right height 1 (chain 3) = 3 edges ✓.

For [1,2,3,4,5], what is the diameter?

3. Best path: 4 → 2 → 1 → 3 with 3 edges. Trying each node as the bend: at node 2 it's 1+1=2, at node 1 it's 2+1=3. The max over all bends is 3.

Why is calling a separate height() for every node wasteful?

Heights get recomputed over and over → O(n²); computing the diameter DURING one height traversal reuses each height → O(n). height(root) already visits every node, calling it again per node repeats that work n times. The one-pass trick: while computing heights bottom-up, let every node try itself as the bend using the two heights it just computed.

Related problems

Keep practising