Wait, What?
One carefully chosen vertex can make every remaining piece of a tree at most half as large.
That single fact is the doorway into centroid decomposition. Instead of treating a tree as one fixed rooted object, we repeatedly choose a balanced separator, remove it conceptually, and recurse on the smaller components. The result is a second tree—the centroid tree—that turns many difficult distance and path questions into a short chain of progressively larger regions.
Quick Answer
Learn centroid decomposition in this order: tree centroid → subtree sizes → balanced separator property → recursive decomposition → centroid-tree depth → distance-to-ancestor bookkeeping → query/update patterns → complexity → implementation discipline. The key is not memorising code. It is understanding why each recursive component shrinks by at least half.
1. Start With the Object: a Tree Centroid
For a tree with n vertices, a centroid is a vertex whose removal leaves connected components containing at most n/2 vertices each. Every tree has at least one centroid; some trees have two.
This is different from an ordinary root. A root is a viewpoint. A centroid is a balance property. If you root a long path at one end, almost the entire tree lies below the first few vertices. Choose the middle vertex as a centroid and the two sides are balanced.
2. The First Invariant: No Remaining Component Is Too Large
The decomposition works because after selecting a centroid c, every component of the tree with c removed has size at most half the current component. When we recurse, the same guarantee applies again.
That gives a structural invariant worth saying aloud while tracing: each step moves into a component at most half the size of its parent component. Therefore a vertex can belong to only O(log n) nested decomposition components.
3. Find a Centroid With Subtree Sizes
A standard implementation temporarily roots the current component, computes subtree sizes, and then walks toward any child whose subtree is larger than half the component. If such a heavy side exists, the current vertex cannot be the centroid; move into that side. When no side exceeds half, the current vertex is a centroid.
subtree_size(v, parent):
size[v] = 1
for u in adj[v]:
if u != parent and not removed[u]:
subtree_size(u, v)
size[v] += size[u]
find_centroid(v, parent, total):
for u in adj[v]:
if u != parent and not removed[u] and size[u] > total / 2:
return find_centroid(u, v, total)
return vProfessional implementations must also account for the “parent side”—the vertices outside a child subtree. The recursive walk above is safe because it starts from a subtree-size computation for the current component and always follows a child larger than half.
4. Build the Centroid Tree
Once the centroid is found, mark it as removed from the current component. Every still-active neighbour now belongs to a smaller component. Recursively decompose each one, and connect its centroid to the current centroid in the centroid tree.
decompose(start, centroid_parent):
total = compute_sizes(start)
c = find_centroid(start, NONE, total)
parent_in_centroid_tree[c] = centroid_parent
removed[c] = true
for u in adj[c]:
if not removed[u]:
decompose(u, c)The original edges do not become centroid-tree edges. The centroid tree records the history of balanced recursive separation, not the original neighbourhood structure.
5. Why the Centroid Tree Has Logarithmic Height
Suppose a vertex begins in a component of size n. After one decomposition level it lies in a component of size at most n/2, then at most n/4, then n/8, and so on. After O(log n) halvings the component contains one vertex.
This is the reason centroid decomposition is useful. A query can often be answered by looking only at the O(log n) centroid ancestors of the target vertex instead of walking through the original tree.
6. Trace a Small Tree by Hand
Take a seven-vertex path 1–2–3–4–5–6–7. Vertex 4 is a centroid: removing it leaves {1,2,3} and {5,6,7}. The left component has centroid 2; the right component has centroid 6. The singleton components then become leaves.
The resulting centroid tree is shallow even though the original path has diameter six. This is an important mental shift: centroid decomposition does not shorten distances in the original tree. It shortens the number of regions a query must inspect.
7. The Classic Query Pattern: Nearest Marked Vertex
Suppose the original tree is static and vertices can become marked. We want the distance from a query vertex v to the nearest marked vertex.
For every centroid c, maintain the best known distance from c to any marked vertex. When a vertex x is marked, walk from x through its centroid ancestors and update each centroid with dist(x,c). To query v, walk through the same ancestor chain and minimize:
best[c] + dist(v,c)
Why is this safe? For any marked vertex x, there is some centroid level at which the decomposition separates v and x, and their path is represented through that separator. The centroid chain gives a small family of separators guaranteed to include the useful one.
8. Cache Distances, or Pay for Them Repeatedly
If distance from a vertex to each centroid ancestor is precomputed during decomposition, an update or query can inspect O(log n) ancestors with O(1) distance lookup at each level. This commonly gives O(log n) query/update time and O(n log n) stored distance information.
If distances are recomputed using another structure such as LCA, an extra logarithmic factor may appear. Always state which distance model your complexity claim assumes.
9. Deletions Are Harder Than Insertions
For “mark only” problems, a centroid can store one minimum value and updates are monotonic. If vertices may be unmarked, a single minimum is insufficient because the current winner may disappear. A common production design stores a multiset, heap with lazy deletion, or another structure per centroid so the current minimum can be repaired safely.
10. Complexity: Separate Construction, Storage and Operations
- Standard decomposition construction: O(n log n) with ordinary subtree-size recomputation across levels.
- Centroid-tree height: O(log n).
- Stored vertex-to-centroid distances: commonly O(n log n).
- Nearest-marked update/query: commonly O(log n) with cached distances and monotonic marking.
- Original tree: unchanged; decomposition is auxiliary structure.
11. Know When Not to Use It
- Use an Euler tour plus Fenwick/segment tree for many subtree-aggregate jobs.
- Use heavy-light decomposition when the core operation is an online aggregate along arbitrary paths.
- Use binary lifting/LCA when the main need is ancestor or distance queries.
- Centroid decomposition is strongest when a static tree can be split around balanced separators and each query can be summarized through those separators.
12. How to Learn It Without Copying a Template
Programming-education research supports a progression from worked examples and code tracing toward independent construction. Subgoal-labelled worked examples have improved early problem-solving performance in programming, while PRIMM-style teaching begins with predicting and investigating existing code before asking learners to make their own. Apply that here: first label the subgoals measure component → find balance point → remove → recurse → store ancestor information → answer through ancestors; then trace them on tiny trees before coding.
Common Failure States
- Confusing the original tree root with a centroid.
- Forgetting that the centroid is chosen relative to the current component, not the whole original tree.
- Using subtree sizes computed before earlier centroids were removed.
- Connecting centroid-tree nodes according to original adjacency instead of recursive parentage.
- Claiming O(log n) queries while recomputing distances in O(log n) at every centroid level.
- Using one stored minimum when unmark operations can invalidate it.
- Recursing deeply in the original DFS on a path-shaped tree without considering language stack limits.
Practice Ladder
- Beginner: find every valid centroid of paths, stars and balanced trees by hand.
- Foundation: implement subtree sizes and centroid finding for one component.
- Intermediate: build the centroid tree and print each vertex’s centroid parent and level.
- Advanced: solve nearest-marked-vertex queries with cached distances.
- Professional: support deletions, weighted edges, memory-conscious distance storage and adversarial path-shaped inputs.
- Verification: for small random trees, compare each query against an O(n) breadth-first-search or all-pairs baseline.
Learning Hall Boundary
This article owns centroid decomposition as a balanced static-tree algorithmic technique: centroid selection, recursive separator structure, centroid-tree reasoning and representative distance-query patterns. It does not replace the Learning Hall’s existing learner-state, study-interface, calibration, heavy-light decomposition, LCA or general divide-and-conquer teaching jobs.
Evidence Boundary
The balanced-separator idea is standard tree-algorithm theory and appears in research uses of centroid decomposition such as Goodrich and Tamassia’s work on dynamic trees and point location. Contemporary algorithm teaching commonly uses the O(n log n) recursive construction and logarithmic centroid-tree depth. For instruction design, useful evidence includes Morrison, Margulieux and colleagues on subgoal-labelled worked examples in programming, including the 2020 International Journal of STEM Education study, and Sentance, Waite and Kallia’s PRIMM work presented at SIGCSE 2019.
Professional rule: you understand centroid decomposition when you can prove the halving property, explain what the centroid tree represents, and derive the query formula from separators rather than from memorised code.
