Exercise 967Combinatorics › Graph theoryL1Added 3 Nov 2026

Diameter of a tree

#tree#diameter#BFS

Statement

Show that the diameter of a tree (longest shortest path) can be found by two BFS runs.

Hint

First BFS from any vertex; the farthest vertex is an endpoint of a diameter. Second BFS from there.

Show solutionHide solution

First BFS. Start from any vertex $r$ , find farthest vertex $u$ .

Claim. $u$ is an endpoint of a diameter.

Second BFS. Start from $u$ , find farthest vertex $v$ . Then $d(u,v)$ is the diameter.

Conclusion. Two BFS runs compute the diameter of a tree in $O(|V|)$ .