Finding the Centroid

A centroid is a node $c$ where every subtree has at most $n/2$ nodes after removing $c$. To find it:

$1.$ Pick any root and compute subtree sizes

$2.$ Start at the root

$3.$ If any child's subtree has $> n/2$ nodes, move to that child

$4.$ Otherwise, current node is the centroid

Why does this work? At each step, you move toward larger subtrees. When you stop, no subtree exceeds $n/2$ nodes, so you're at a centroid. Time: $O(n)$ for computing sizes and finding centroid.