The Two-BFS Trick

Here is the core idea: start BFS from any random node. Find the farthest node from it. Call that node $u$. Now run BFS from $u$ and find the farthest node from $u$. Call that $v$. The distance from $u$ to $v$ is the diameter.

Two BFS runs instead of $n$ runs. That is $O(n)$ total time.

This works because one endpoint of the longest path will always be the farthest node from your starting point. I'll prove why in the next unit.

Space complexity is $O(n)$ for the data structures used.