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. (Note that here the tree's height, 4 nodes on 7 → 3 → 4 → 2, and the diameter, 4 edges, happen to be equal. The animation and the walkthrough use the smaller tree [1,2,3,4,5], whose diameter is 3.)

Brute-force approach

The first idea is to walk the tree and, at every node, call a separate height() on its left and right children and add the two (the bend at that node), keeping the biggest. It is correct but re-walks the same subtrees: on the statement example [7,3,9,1,4,null,null,null,null,null,2] the walk visits 6 nodes and the height walks make 9 extra node visits (node 2 is measured 3 times); on a chain of n nodes the height walks make n(n - 1) / 2 extra visits (4,950 for 100 nodes). An even plainer version tries every pair of nodes: n(n - 1) / 2 pairs, each with a walk to measure the distance. (These counts are node visits, empty spots not counted; section 3 of the walkthrough counts calls to height() including the empty children: 22 against 11.)

Steps

  1. At every node, call height() on its left child and on its right child
  2. The bend at that node is leftHeight + rightHeight (edges)
  3. Keep the largest bend over all nodes
  4. Return it

Time complexity: O(n^2) in the worst case · Space complexity: O(h)

Trade-offs

  • Re-measures overlapping subtrees: 9 extra node visits beside 6 on the example, 4,950 extra on a chain of 100
  • The every-pair version is worse still: n(n - 1) / 2 pairs, each needing its own walk

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!
  • A missing child has height 0, never 1: the empty spot adds no node and no edge.
  • The helper's return value at the top is the height of the tree, not the answer: return best, not height(root).

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. In sizes: h is n for a chain, and only about 20 for a balanced tree of a million nodes. In Python a skewed tree of about 1,000 nodes also needs sys.setrecursionlimit (the tests do not go that deep).

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