↩ back to Node-Linked Trees

Centroid Decomposition

The site's twelfth node-linked trees entry, and a different kind of tree-decomposition from its nearest sibling, Heavy-Light Decomposition. HLD flattens a tree into an array so one path at a time becomes a handful of contiguous ranges for a range structure underneath. Centroid Decomposition doesn't touch any range structure at all — it builds a second tree, over the same n nodes, whose shape answers a different question entirely: which small set of nodes does every possible path in the original tree pass through at least one of? Repeatedly find the centroid of whatever's left — the node whose removal splits the remainder into pieces no bigger than half of what came before — remove it, and recurse into each piece independently. The halving guarantees the resulting centroid tree is only O(log n) deep, no matter how skewed the original tree is, which turns "do something for every pair of nodes" from an O(n²) problem into an O(n log n) one.

How it works

Compute subtree sizes with one DFS from any node in the current piece, then walk toward whichever neighbor still carries more than half that piece's size, one step at a time, until no neighbor does — that node is the centroid. (This is the same kind of walk Heavy-Light Decomposition uses to find the heaviest child; here the goal is different — stop as soon as every remaining direction is small enough, not keep following the biggest one.) Mark the centroid removed, record it as a node in the centroid tree (its parent there is whichever centroid was removed one level up, or nothing if this is the very first one), and recurse into each of its still-unremoved neighbors as the root of its own separate piece. A single node left in a piece is trivially its own centroid — the base case that ends every branch of the recursion.

Try it

The same 11-node tree Heavy-Light Decomposition and Binary Lifting both use, laid out identically — so the same shape can be compared against two completely different decompositions of it. The top panel is the original tree: untouched nodes are plain, the node just chosen as a centroid is highlighted, and every centroid removed so far is shaded. The bottom panel is the centroid tree being built underneath it, one node at a time, in the same order.

Why it works

If some neighbor's piece held more than half the current piece's size, the walk would have moved into it instead of stopping — so by construction, every piece left behind by a removal is at most half the size of the piece the centroid was found in. That halving happens at every level of the recursion, on every resulting piece, so the centroid tree's depth is bounded by ⌈log₂ n⌉ — not just usually, structurally. Checked two ways before writing this down: 5,000 randomized trials (n = 1 to 500) plus path graphs — the shape that makes the bound tightest, since a path can't branch its way to a shallower decomposition — at every power-of-two size and its neighbors up to n = 2,048, and zero exceeded ⌈log₂ n⌉ in either set; the path graphs hit the bound exactly at every power of two (depth 10 at n = 1,024, depth 11 at n = 2,048). Separately, across 3,980 randomized trials (n = 2 to 200), every single decomposition made exactly n recursive calls — one centroid per node, never more, never fewer — and an independently-implemented check (a fresh BFS from each surviving neighbor, not a reuse of the same subtree-size array the search itself relied on) confirmed every removal actually left every remaining piece at or under half, with zero violations.

On this page's own 11-node tree: the first centroid is node 2 (component size 11, worst remaining piece size 4, well under the 5.5 half), and the full order is 2, 1, 3, 7, 4, 5, 8, 6, 9, 10, 11 — all 11 nodes, each exactly once. The resulting centroid tree is 4 levels deep (root at depth 0, deepest leaves at depth 3), against ⌈log₂ 11⌉ = 4 — the bound met exactly, not just approached.

Reference implementation

Matches the demo above. removed[] is the one detail every step below depends on — see Pitfalls for what happens without it.

function centroidDecompose(adj, n) {
  const removed = new Array(n + 1).fill(false);
  const subtreeSize = new Array(n + 1).fill(0);
  const ctParent = new Array(n + 1).fill(-1);

  function computeSize(u, parent) {
    subtreeSize[u] = 1;
    for (const v of adj[u]) {
      if (v === parent || removed[v]) continue;      // skip already-removed centroids
      computeSize(v, u);
      subtreeSize[u] += subtreeSize[v];
    }
  }

  function findCentroid(u, parent, compSize) {
    for (const v of adj[u]) {
      if (v === parent || removed[v]) continue;
      if (subtreeSize[v] > compSize / 2) return findCentroid(v, u, compSize);
    }
    return u;                                          // no neighbor carries more than half
  }

  function decompose(start, ctParentNode) {
    computeSize(start, -1);
    const centroid = findCentroid(start, -1, subtreeSize[start]);
    ctParent[centroid] = ctParentNode;
    removed[centroid] = true;
    for (const v of adj[centroid]) {
      if (!removed[v]) decompose(v, centroid);
    }
  }

  decompose(1, -1);
  return ctParent;                    // ctParent[v] = v's parent in the centroid tree
}

Where it's used

Any path between two nodes in the original tree passes through exactly one node that is an ancestor of both of them in the centroid tree (possibly one of the two nodes themselves) — the shallowest centroid the path was ever cut at. That's what makes centroid decomposition useful for questions about every path at once, not just one: process each centroid exactly once, in any order, and every path in the original tree gets accounted for at precisely one of them.

A standard example: counting how many pairs of nodes sit within tree-distance K of each other. At each centroid c, compute every remaining node's distance to c and count pairs whose distances sum to at most K across the whole current piece — then subtract back out the pairs that landed in the same branch of c (computed the identical way, once per branch), since a path between two nodes in the same branch never actually passes through c at all. Recurse, and every pair gets counted at exactly the one centroid its path actually passes through. Verified against a brute-force O(n²) all-pairs BFS across 10,710 trials (n = 2 to 120, six values of K per tree), zero mismatches. On this page's own tree: K = 1 gives 10 pairs, K = 2 gives 22, K = 3 gives 36, K = 4 gives 48 — all four matching the brute-force count exactly. The same walk-up-to-the-root shape (touch each of a node's O(log n) centroid-tree ancestors) also underlies the classic online version of this idea — mark/unmark nodes and ask "what's the nearest marked node to here" after every update — by keeping a running best distance at each ancestor instead of a one-time count.

Pitfalls

Every one of the checks above depends on removed[] actually being consulted — drop it from computeSize and findCentroid (or forget to skip an already-removed neighbor before recursing into it) and the algorithm doesn't just get one piece wrong, it never gets anywhere at all. Without it, computeSize and findCentroid have no way to know any node has ever been removed, so they treat the entire original tree as still connected on every single call, no matter which node they're called from. On this page's own tree, the very first centroid found is still node 2 (correct, since nothing has been removed yet) — but recursing into its neighbors calls decompose on a node that leads straight back through 2 into the whole tree again, which finds the exact same centroid, 2, all over again. Traced with a hard call cap: all 20 capped calls report the identical tuple — component size 11, centroid 2 — zero progress across any of them. Run with no cap at all, it crashes with RangeError: Maximum call stack size exceeded before producing a single line of output, reproduced on every run (deterministic, not a rare stack-depth coincidence) — not a subtly wrong answer, but the loudest possible failure, because the very first recursive step is already a perfect do-nothing loop.

Complexity

Time: every level of the centroid tree partitions the nodes still standing into disjoint pieces, so the total work of computing sizes and finding centroids across one whole level is O(n) — and there are O(log n) levels, for O(n log n) total build time. Space: O(n) for removed[], subtreeSize[], and ctParent[], plus O(log n) recursion depth. Any query that needs to touch every ancestor of a node in the centroid tree costs O(log n) per node touched, since that's exactly the tree's depth — the count-pairs example above does O(size log size) work at each individual centroid (sorting distances for a two-pointer sweep) summing to O(n log n) per level and O(n log² n) overall, while the online nearest-marked-node version does O(log n) work per update or query after the same O(n log n) preprocessing.

This site's guide, Choosing a Search Tree, groups this entry with Binary Lifting, Heavy-Light Decomposition, and Link-Cut Tree as answering questions about a tree's own shape rather than about a set of keys stored in one — none of the four ever compares two keys against each other to decide which way to branch. Among them, it builds a second, shallower tree over the same nodes specifically to answer questions about every path at once, not just ancestor queries or a single flattened path.