Graph Theory37 sections · 1633 units
Open in Course

CSES 1131 Tree Diameter - Why Double BFS Works

Intuition behind the algorithm

The farthest node from any starting point must be one endpoint of the diameter path. Here is the intuition: if there were a longer path elsewhere, the triangle inequality on trees would mean your BFS would have found a node at least as far.

This property is unique to trees. In general graphs with cycles, the farthest node from a random start is not guaranteed to be a diameter endpoint. Trees have exactly one path between any pair of nodes, which makes this argument work.