A centroid is a node where every subtree has at most nodes after removing . To find it:
Pick any root and compute subtree sizes
Start at the root
If any child's subtree has nodes, move to that child
Otherwise, current node is the centroid Why does this work? At each step, you move toward larger subtrees. When you stop, no subtree exceeds nodes, so you're at a centroid. Time: for computing sizes and finding centroid.