Diameter of Binary Tree

EasyTreesTreeDFSBinary Tree

Problem

Given the root of a binary tree, find the length of the longest path between any two nodes, counted in edges. The path need not pass through the root, and it may bend once at some node, going down into the left subtree on one side and the right subtree on the other.

Example. A root 1 with left child 2 and right child 3, where 2 also has children 4 and 5, has diameter 3: the path 4 to 2 to 1 to 3 (or 4 to 2 to 5) has three edges.

Key idea

Checking every pair of nodes and computing the path between them is wasteful, since most pairs share large stretches of the tree. The longest path through any given node is fully determined by how tall its left and right subtrees are: it equals the left height plus the right height, since the path can descend to the deepest leaf on each side and meet at that node.

So compute subtree heights bottom-up, and at every node also check whether left height plus right height beats the best diameter seen so far. The height computation needed anyway, one plus the deeper child, doubles as the input to that check, so one traversal handles both jobs: returning height upward, and updating a running maximum as a side effect.

Solution

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function diameterOfBinaryTree(root: TreeNode | null): number {
  // tracks the best diameter seen across every node visited so far
  let diameter = 0;

  function height(node: TreeNode | null): number {
    if (node === null) {
      return 0;
    }

    const leftHeight = height(node.left);
    const rightHeight = height(node.right);

    // the longest path through this node joins its two deepest sides
    diameter = Math.max(diameter, leftHeight + rightHeight);

    return 1 + Math.max(leftHeight, rightHeight);
  }

  height(root);

  return diameter;
}

Complexity

  • Time: O(n). Each node's height is computed once, in a single post-order pass.
  • Space: O(h). The recursion stack depth matches the tree's height.

Watch out for

  • The diameter is measured in edges, not node count: do not off-by-one it into a node count.
  • The best path frequently does not pass through the root; tracking a running maximum across every node, not just the root's combined height, is essential.
  • Treat a null child's height as 0 so a leaf correctly reports height 1 and diameter 0.

Pattern

This is the compute-and-combine pattern: a bottom-up value, here height, is needed for the recursion anyway, and a global answer rides along as nodes are visited. The same trick of piggybacking a running answer onto a required recursive computation reappears in binary tree maximum path sum.

Related questions