CSES 1131 Tree Diameter - Walkthrough - Tree Diameter & Center | Graph Theory

Example tree: edges ( $1$ , $2$ ), ( $1$ , $3$ ), ( $3$ , $4$ ), ( $3$ , $5$ ).

First BFS from node $1$ : distances are { $1$ : $0$ , $2$ : $1$ , $3$ : $1$ , $4$ : $2$ , $5$ : $2$ }. Farthest nodes are $4$ and $5$ (distance $2$ ). Pick $u = 4$ .

Second BFS from node $4$ : distances are { $4$ : $0$ , $3$ : $1$ , $1$ : $2$ , $5$ : $2$ , $2$ : $3$ }. Farthest node is $2$ (distance $3$ ). The diameter is $3$ : the path $4$ - $3$ - $1$ - $2$ .

Notice how starting from an arbitrary node ( $1$ ) found an endpoint ( $4$ ), and BFS from there found the true diameter.