Tree Diameter — Longest Path Between Any Two Nodes

The insight

Diameter through node = height(left) + height(right). Track max as we compute heights.

Implementation

int diameter = 0;
int height(Node n) {
  if (n == null) return 0;
  int leftH = height(n.left);
  int rightH = height(n.right);
  diameter = max(diameter, leftH + rightH);
  return 1 + max(leftH, rightH);
}

Return in edges vs nodes

Path length in edges vs nodes differs by 1. Read problem carefully.

Diameter in general graph

Two BFS approach: BFS from any node u to find farthest v; BFS from v to find farthest w; distance(v, w) = diameter. Works only for trees.