Diameter of a binary tree

Medium TimeO(n) SpaceO(h)

The diameter of a tree is the longest path between any two nodes, counted in edges. It need not pass through the root — the longest path may sit entirely inside one subtree — and it bends at most once, at the highest node it reaches. Given a binary tree, return its diameter.

Examples

Example 1

Input
root = buildTree()
Output
4
1 → 2 → 4 → 7 → 6 is 4 edges, and nothing in the tree runs longer.

Example 2

Input
root = buildTree().left
Output
2
1 → 2 → 3 is 2 edges, which is the longest the left subtree holds on its own.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function diameter(root) {
  let best = 0;
  function depth(node) {
    if (node === null) return 0;
    const left = depth(node.left);
    const right = depth(node.right);
    if (left + right > best) best = left + right;
    return Math.max(left, right) + 1;
  }
  depth(root);
  return best;
}
diameter(buildTree());
Done

The first 9 calls, of 17. This one does not fit on a page.

Step through diameter(buildTree()) call by call

More like this

All binary trees examples (9) →