Graph Theory37 sections · 1633 units
Open in Course

What is a Centroid?

(The balance point of a tree)

A centroid of a tree is a node where removing it splits the tree into components, each with at most n/2n/2 nodes. Every tree with nn nodes has at least one centroid, sometimes two. Think of it as the balance point. No subtree gets too heavy. This property is what makes divide-and-conquer efficient.

When you remove a centroid, you split the problem into smaller, balanced subproblems. For a tree with 55 nodes arranged as a star (one center, four leaves), the center is the centroid. Remove it and you get four components of size 11 each, all well under 5/2=2.55/2 = 2.5.