Diameter of Binary Tree

Examples

Input: root = [1,2,3,4,5]
Output: 3

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

Input: root = [1,2]
Output: 1

The only path is 1 -> 2, a single edge.

Input: root = [1]
Output: 0

A single node has no path at all.

Constraints

• The number of nodes in the tree is in the range [1, 10^4].

• -100 <= Node.val <= 100

Approach

It's tempting to think the longest path must run through the root, but it can be tucked entirely inside one subtree. The key realization is that for any node, the longest path passing through it is exactly its left subtree height plus its right subtree height. So the answer is the maximum of that quantity over every node in the tree.

Rather than recomputing heights over and over (which would be slow), compute each subtree's height with a single recursive pass, and update a running "best diameter seen so far" value at every node along the way, using the same height numbers you just calculated.

Solutions

Brute Force — Height From Every Node

For each node, compute the height of its left and right subtrees separately (each a full recursive call) and combine them. This recomputes heights repeatedly, which is wasteful.

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

function height(node) {
  if (node === null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

function diameterOfBinaryTree(root) {
  if (root === null) return 0;

  const throughRoot = height(root.left) + height(root.right);
  const bestInLeft = diameterOfBinaryTree(root.left);
  const bestInRight = diameterOfBinaryTree(root.right);

  return Math.max(throughRoot, bestInLeft, bestInRight);
}

Time: O(n²) — height() is called on overlapping subtrees repeatedly · Space: O(h) — recursion stack depth

Optimal — Height + Diameter in One Pass

Write a helper that returns a subtree's height, but also updates a shared 'best diameter' value each time it's called, using the heights of the current node's two children.

function diameterOfBinaryTree(root) {
  let best = 0;

  function height(node) {
    if (node === null) return 0;

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

    best = Math.max(best, leftHeight + rightHeight);

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

  height(root);
  return best;
}

Time: O(n) · Space: O(h) — recursion stack depth, where h is the tree's height (O(n) worst case)