Graph Theory37 sections · 1633 units
Open in Course

CSES 1131 Tree Diameter - Core Idea

Apply two-BFS directly

The core idea: start BFS from any node and find the farthest node uu. Then run BFS from uu to find the farthest node vv. The distance from uu to vv is the diameter.

Why does this work? The farthest node from any starting point must be a diameter endpoint. This is a property of trees that fails for general graphs. The proof involves showing that any path not ending at uu or vv cannot be longer than the uu-vv path. You do not need to understand the proof to use the technique.