Skip to content
Tutorials Center
My learning

Topics

Lesson 201 of 225 ยท Advanced Topics

Centroid Decomposition

Learn centroid decomposition in Python: split a tree at its centroid, build the centroid tree of depth O(log n) and answer nearest-marked-node queries.

Many tree questions are about pairs of nodes: how many pairs are exactly k apart, which marked node is closest to this one, what is the sum of all pairwise distances? Looking at each pair is O(nยฒ). Divide and conquer works beautifully on arrays because you can cut an array in half. Centroid decomposition is the way to cut a tree in "half".

The idea: find a node whose removal splits the tree into pieces that are each at most half the original size. Handle every path that passes through that node, then recurse into the pieces. Because sizes at least halve, the recursion is only O(log n) levels deep, and the total work is often O(n log n).

The centroid

A centroid of a tree with n nodes is a node such that, after removing it, every remaining component has at most n / 2 nodes. Every tree has at least one (and at most two, adjacent to each other).

Why does one exist? Start at any node. If some neighboring component is bigger than n / 2, step into that component. You can never step back, because the part behind you is smaller than half (you just moved away from the big side). The tree is finite, so you stop somewhere, and that node is a centroid.

To find it you need subtree sizes. We compute them with a loop rather than recursion, so even a path of 100,000 nodes works in Python.

The decomposition and the centroid tree

The algorithm:

  1. Find the centroid c of the current component.
  2. Handle all paths that go through c (this is the problem-specific part).
  3. Mark c as removed and repeat for each remaining component.

Writing "centroid c was the parent of the centroid found in each sub-component" gives a new tree, the centroid tree. It has the same nodes as the original but a different shape. Its height is at most floor(log2 n) + 1, because each level has components at most half the size of the level above.

For a path of 7 nodes numbered 0 to 6, the middle node 3 is the centroid; it splits the path into 0-1-2 and 4-5-6, whose centroids are 1 and 5, and so on:

flowchart TD
    subgraph Original["Original tree: a path"]
        direction LR
        p0((0)) --- p1((1)) --- p2((2)) --- p3((3)) --- p4((4)) --- p5((5)) --- p6((6))
    end
    subgraph Centroid["Centroid tree"]
        c3((3)) --> c1((1))
        c3 --> c5((5))
        c1 --> c0((0))
        c1 --> c2((2))
        c5 --> c4((4))
        c5 --> c6((6))
    end

A path of seven nodes becomes a perfectly balanced centroid tree of height 3. The same shape appears for any tree: a deep and thin original turns into a shallow one.

The key property: for any two nodes u and v in the original tree, the path between them passes through their lowest common ancestor in the centroid tree. Think of it this way: the first centroid that was removed from a component containing both u and v is the one that separates them (or equals one of them), so the path is cut exactly there. This is why you can answer path questions with "go through a centroid ancestor".

Python Build the centroid tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The walk in step 2 starts from any node of the component and moves toward the heavy side. That is the argument we made earlier, written as a loop. Every component is sized once per level, and a node belongs to one component per level, so the whole decomposition is O(n log n).

Using it: nearest marked node

A classic problem: nodes start unmarked ("white"). Two kinds of operations arrive in any order:

  • mark(v): paint node v red.
  • nearest(v): how far is the closest red node from v? (The distance counts edges.)

Because the path from v to any red node r passes through a centroid-tree ancestor of both, the shortest distance is

TEXT
min over centroid ancestors a of v:  dist(v, a) + best[a]

where best[a] is the smallest distance from a to a red node that lies in a's component. Each node has only O(log n) centroid ancestors, so:

  • mark(v): for each centroid ancestor a of v, set best[a] = min(best[a], dist(v, a)). O(log n).
  • nearest(v): take the minimum above. O(log n).

The path from v to the red node may be shorter than the route through a (when the real path never touches a), but then it is also counted at a closer ancestor, so taking the minimum over all ancestors gives exactly the true distance. We never under-count, because dist(v,a) + best[a] is the length of a real walk.

We need the distance from each node to each of its centroid ancestors. We get them for free: when we pick a centroid c, a BFS from c through its component gives the distance to every node in it. Store (c, distance) in each node's list.

Python Nearest red node with the centroid tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The class stores about n log n pairs in total. Each mark and nearest loops over at most that many ancestors for one node, which is why both operations are O(log n) instead of the O(n) BFS in the brute force.

Counting paths through a centroid

The same machinery solves "how many pairs of nodes are exactly k apart?". For a centroid c, compute the distance from c to every node of its component. Two nodes u and v in different child components with d(u) + d(v) = k form a counted path through c. You count them with a frequency array of distances, subtracting pairs that lie in the same child component (which share a prefix that is not a valid path through c). Doing this at every level gives O(n log n) or O(n logยฒ n) in total, depending on how you count. The pattern "handle paths through the centroid, then recurse on the pieces" is the same every time; only step 2 changes.

Comparison with other tree techniques

Technique Good for Typical cost
Binary lifting ancestors, LCA, distance on a static tree O(log n) per query
Heavy-light decomposition path updates and queries O(logยฒ n) per query
Centroid decomposition counting or optimizing over pairs of nodes, nearest marked node O(log n) per update/query after O(n log n) build
Tree DP per-subtree answers, rerooting O(n)

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What defines a centroid of a tree with n nodes?

    Removing a centroid splits the tree into pieces that are each at most half the size, which is what makes the recursion depth logarithmic.
  2. 2. What is the height of the centroid tree of a path with 1,000 nodes?

    Each level halves the component size, so the height is floor(log2 n) + 1, which is 10 for n = 1,000.
  3. 3. For nodes u and v, which node of the centroid tree is guaranteed to lie on the path between them in the original tree?

    The first centroid removed from a component that contains both u and v separates them (or is one of them), so the path passes through it.
  4. 4. In the nearest-red-node problem, why is the nearest(v) result never too small?

    Going from v to the centroid a and then to the red node recorded in best[a] is a real walk, so it is never shorter than the true shortest path, and the true shortest path is found at one of the ancestors.

Summary

  • A centroid is a node whose removal leaves components of at most n / 2 nodes; one always exists and is found by walking toward the heavy side.
  • Centroid decomposition removes a centroid, handles the paths through it, and recurses on the components, for O(n log n) in total.
  • The centroid tree has height O(log n), and the path between any two nodes passes through their LCA in the centroid tree.
  • Store (centroid ancestor, distance) for each node: every update and query then walks only O(log n) ancestors.
  • Typical uses: nearest marked node, counting pairs at distance k, and sums of pairwise distances.

Next: Project: Autocomplete