Algorithm - Find Centroid

$1.$ DFS from any root to compute subtree sizes for all nodes.

Store them in an array for quick lookup. This is a standard tree traversal.

$2.$ Start at the root.

While the current node $v$ has a child $u$ with size[u] > n/2, move to $u$. When no such child exists, return $v$ as the centroid. The first phase takes $O(n)$ time for the tree traversal. The second phase visits at most $n$ nodes in the worst case (imagine a line graph where you walk the entire length), so total time is $O(n)$.

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