CSES 1131 Tree Diameter - Algorithm

$1.$ Build adjacency list from the $n-1$ edges.

$2.$ Run BFS from node $1$, track distances, find node $u$ with maximum distance.

$3.$ Run BFS from $u$, track distances, find node $v$ with maximum distance.

$4.$ Return dist[v] as the diameter. Two BFS traversals, each $O(n)$. Total time: $O(n)$. Space: $O(n)$ for adjacency list and distance array. This beats the naive $O(n^2)$ approach decisively.