543. Diameter of Binary Tree

Return the diameter of a binary tree: the number of edges on the longest path between any two nodes. The path may or may not pass through the root.

A post-order DFS returns each subtree's depth. On the way up, update the best diameter with left + right at that node.

1function diameterOfBinaryTree(root: TreeNode | null): number {
2  let best = 0;
3  function dfs(n: TreeNode | null): number {
4    if (!n) return 0;
5    const l = dfs(n.left), r = dfs(n.right);
6    best = Math.max(best, l + r);
7    return 1 + Math.max(l, r);
8  }
9  dfs(root);
10  return best;
11}

best = 0

tree (d = depth)

best = 0.

1 / 0

Space: play/pause · ←/→: step