Introduction

A tree is one of the simplest data structures: nn nodes connected by n−1n-1 edges, no cycles, a unique path between every pair of nodes. Trees turn up everywhere — file systems, family pedigrees, parse trees in compilers, phylogenetic trees in biology.

Now ask a natural question: how many paths in the tree have exactly length kk? A path here is any sequence of distinct adjacent nodes. The naive answer visits every pair of nodes and measures the distance between them — O(n2)O(n^2) work, which becomes painfully slow the moment nn climbs into the millions.

The clever answer is centroid decomposition, a divide-and-conquer technique that cuts the tree at precisely the right node and lets you count every path in O(nlog⁡n)O(n \log n) time. The key insight is deceptively simple: every path either passes through the centroid of the current tree, or it lives entirely in one of the smaller subtrees left after you remove it. Solve the first kind, recurse on the second.

Try It: Count Paths of Length k

The tree below has 11 nodes. Pick a target length kk and press Run to watch centroid decomposition count every path of that length. The centroid at each recursive level is highlighted in orange; paths that cross it are tallied before the algorithm recurses into the remaining subtrees.

<div class="controls">
  <label>Target length k: <input id="kInput" type="number" min="1" max="6" value="3"></label>
  <button id="runBtn" type="button">Run</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div class="layout">
  <canvas id="treeCanvas" width="480" height="260"></canvas>
  <div class="panel">
    <div id="logBox" class="logbox"></div>
    <div class="result" id="result"></div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; }
#kInput { width: 3.5rem; padding: .25rem .4rem; font-size: .9rem; border: 1px solid #aaa; border-radius: 5px; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.layout { display: flex; gap: .8rem; flex-wrap: wrap; }
canvas { border: 1px solid #dde; border-radius: 8px; background: #f8fafc; flex-shrink: 0; max-width: 100%; }
.panel { flex: 1 1 160px; display: flex; flex-direction: column; gap: .5rem; }
.logbox { font-size: .8rem; line-height: 1.55; color: #334; background: #f4f6f8;
          border: 1px solid #dde; border-radius: 7px; padding: .5rem .7rem;
          max-height: 190px; overflow-y: auto; }
.logbox p { margin: 0 0 .2rem; }
.logbox .hi { color: #d97706; font-weight: 600; }
.logbox .found { color: #0a7d33; font-weight: 600; }
.result { font-size: 1rem; font-weight: 700; color: #1d3557; min-height: 1.4em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Centroid Decomposition — count paths of exactly length k in an 11-node tree.
// Tree edges: 0-1, 0-2, 1-3, 1-4, 2-5, 2-6, 3-7, 3-8, 6-9, 6-10
// Verified: matches brute-force for all k=1..8.
const N = 11;
const EDGES = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[3,8],[6,9],[6,10]];
const POS = [
  [240,24],[140,80],[340,80],[80,148],[200,148],
  [290,148],[400,148],[50,220],[120,220],[365,220],[435,220]
];
const adj = Array.from({length:N},()=>[]);
for(const [u,v] of EDGES){ adj[u].push(v); adj[v].push(u); }

const canvas = document.getElementById('treeCanvas');
const ctx = canvas.getContext('2d');
const logBox = document.getElementById('logBox');
const resultEl = document.getElementById('result');

let highlightCentroid = -1;
let removed = new Set();
let log = [];

// BFS distances from src, skipping removed nodes
function bfsDist(src, rem){
  const dist=new Array(N).fill(-1); dist[src]=0;
  const q=[src];
  for(let i=0;i<q.length;i++){
    const u=q[i];
    for(const v of adj[u]) if(!rem.has(v)&&dist[v]===-1){dist[v]=dist[u]+1;q.push(v);}
  }
  return dist;
}

// Find the centroid of the component containing root (outside rem)
function findCentroid(root, rem){
  // BFS to get component order and parent tree
  const order=[], parent=new Array(N).fill(-1);
  const q=[root]; const seen=new Set([root,...rem]);
  while(q.length){ const u=q.shift(); order.push(u); for(const v of adj[u]) if(!seen.has(v)){seen.add(v);parent[v]=u;q.push(v);} }
  const n=order.length;
  const sz=new Array(N).fill(0);
  for(const u of order) sz[u]=1;
  for(let i=order.length-1;i>=1;i--) sz[parent[order[i]]]+=sz[order[i]];
  for(const u of order){
    let maxSub=0;
    for(const v of adj[u]){ if(rem.has(v)) continue; const cs=parent[v]===u?sz[v]:n-sz[u]; if(cs>maxSub)maxSub=cs; }
    if(maxSub<=n/2) return {centroid:u, compSize:n};
  }
  return {centroid:order[0], compSize:n};
}

// Count unordered pairs at distance k passing through centroid c.
// Uses freq-table inclusion-exclusion: total pairs - same-subtree pairs.
function countThrough(c, rem, k){
  const distC=bfsDist(c,rem);
  const compNodes=[c];
  for(let i=0;i<N;i++) if(!rem.has(i)&&i!==c&&distC[i]>=0) compNodes.push(i);

  // freq[d] = nodes at distance d from c in this component
  const freq=new Array(k+2).fill(0);
  for(const u of compNodes) if(distC[u]<=k) freq[distC[u]]++;

  // ordered pairs (u,v) with distC[u]+distC[v]=k
  let total=0;
  for(const u of compNodes){ const d=distC[u]; if(d>k) continue; const need=k-d; if(need<=k) total+=freq[need]; }

  // subtract ordered pairs that lie entirely within one child-subtree
  const remC=new Set([...rem,c]);
  let sameSub=0;
  for(const nb of adj[c]){
    if(rem.has(nb)) continue;
    const dNb=bfsDist(nb,remC);
    // distance from c for nodes in this subtree = 1 + dNb[u]
    const subFreq=new Array(k+2).fill(0);
    subFreq[1]++; // nb at dist 1 from c
    for(let i=0;i<N;i++) if(!remC.has(i)&&i!==nb&&dNb[i]>=0){ const d=1+dNb[i]; if(d<=k) subFreq[d]++; }
    const subNodes=[nb];
    for(let i=0;i<N;i++) if(!remC.has(i)&&i!==nb&&dNb[i]>=0) subNodes.push(i);
    for(const u of subNodes){
      const du=u===nb?1:1+dNb[u]; if(du>k) continue;
      const need=k-du; if(need>=0&&need<=k) sameSub+=subFreq[need];
    }
  }
  return (total - sameSub) / 2;
}

function drawTree(){
  const W=canvas.width, H=canvas.height;
  ctx.clearRect(0,0,W,H);
  for(const [u,v] of EDGES){
    const bothActive=!removed.has(u)&&!removed.has(v);
    ctx.beginPath();
    ctx.strokeStyle=bothActive?'#9ab':'#dde'; ctx.lineWidth=bothActive?2:1;
    ctx.moveTo(POS[u][0],POS[u][1]); ctx.lineTo(POS[v][0],POS[v][1]); ctx.stroke();
  }
  for(let i=0;i<N;i++){
    const [x,y]=POS[i];
    ctx.beginPath();
    if(removed.has(i)){ ctx.fillStyle='#e2e8f0'; ctx.strokeStyle='#cbd5e1'; ctx.lineWidth=1.5; }
    else if(i===highlightCentroid){ ctx.fillStyle='#f97316'; ctx.strokeStyle='#c2410c'; ctx.lineWidth=2.5; }
    else { ctx.fillStyle='#dbeafe'; ctx.strokeStyle='#3b82f6'; ctx.lineWidth=1.8; }
    ctx.arc(x,y,17,0,2*Math.PI); ctx.fill(); ctx.stroke();
    ctx.fillStyle=removed.has(i)?'#94a3b8':'#1e3a5f';
    ctx.font='bold 12px system-ui'; ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(i,x,y);
  }
}

function addLog(html){ log.push(html); logBox.innerHTML=log.map(l=>`<p>${l}</p>`).join(''); logBox.scrollTop=logBox.scrollHeight; }
function sleep(ms){ return new Promise(r=>setTimeout(r,ms)); }

let running=false;
async function decompose(root, rem, k){
  if(!rem) rem=new Set();
  const {centroid,compSize}=findCentroid(root,rem);
  highlightCentroid=centroid; drawTree();
  addLog(fmt('<span class="hi">Centroid: node %centroid%</span> (%compSize% nodes)', { centroid: centroid, compSize: compSize }));
  await sleep(650);

  const cnt=countThrough(centroid,rem,k);
  if(cnt>0) addLog(fmt('<span class="found">+%cnt% path%v% of length %k% through node %centroid%</span>', { cnt: cnt, v: cnt!==1?'s':'', k: k, centroid: centroid }));
  else addLog(fmt('0 paths of length %k% through node %centroid%', { k: k, centroid: centroid }));
  await sleep(350);

  const remC=new Set([...rem,centroid]);
  removed.add(centroid); highlightCentroid=-1; drawTree();
  await sleep(200);

  for(const nb of adj[centroid]){
    if(rem.has(nb)) continue;
    await decompose(nb,remC,k);
  }
  return cnt;
}

async function run(){
  if(running) return;
  running=true;
  const k=Math.max(1,Math.min(6,parseInt(document.getElementById('kInput').value,10)||3));
  log=[]; logBox.innerHTML=''; resultEl.textContent='';
  removed=new Set(); highlightCentroid=-1; drawTree();

  // run decomposition and accumulate total
  let total=0;
  async function go(root,rem){
    if(!rem) rem=new Set();
    const {centroid,compSize}=findCentroid(root,rem);
    highlightCentroid=centroid; drawTree();
    addLog(fmt('<span class="hi">Centroid: node %centroid%</span> (%compSize% nodes)', { centroid: centroid, compSize: compSize }));
    await sleep(650);
    const cnt=countThrough(centroid,rem,k);
    total+=cnt;
    if(cnt>0) addLog(fmt('<span class="found">+%cnt% path%v% of length %k% through node %centroid%</span>', { cnt: cnt, v: cnt!==1?'s':'', k: k, centroid: centroid }));
    else addLog(fmt('0 paths of length %k% through node %centroid%', { k: k, centroid: centroid }));
    await sleep(350);
    const remC=new Set([...rem,centroid]);
    removed.add(centroid); highlightCentroid=-1; drawTree();
    await sleep(200);
    for(const nb of adj[centroid]){ if(!rem.has(nb)) await go(nb,remC); }
  }
  await go(0,new Set());
  highlightCentroid=-1; removed=new Set(); drawTree();
  resultEl.textContent=fmt('Total paths of length %k%: %total%', { k: k, total: total });
  addLog(fmt('<b>Done. Total: %total% path%v% of length %k%.</b>', { total: total, v: total!==1?'s':'', k: k }));
  running=false;
}

document.getElementById('runBtn').addEventListener('click',run);
document.getElementById('resetBtn').addEventListener('click',()=>{
  running=false; removed=new Set(); highlightCentroid=-1;
  log=[]; logBox.innerHTML=''; resultEl.textContent=''; drawTree();
});
drawTree();
Result
Console

Notice the depth of the recursion: the centroid splits the tree so that no subtree has more than half the nodes, so the recursion is at most O(log⁡n)O(\log n) levels deep. At each level the algorithm scans every node once, giving O(n)O(n) work per level and O(nlog⁡n)O(n \log n) total — regardless of the shape of the tree.

The Real Complexity

The efficiency of centroid decomposition rests on one provable fact about trees:

Centroid existence theorem. Every tree with n≥1n \ge 1 nodes has at least one centroid — a node whose removal leaves no subtree with more than ⌊n/2⌋\lfloor n/2 \rfloor nodes. It can be found in O(n)O(n) by a single DFS that computes subtree sizes.

That guarantee means each recursive call receives a tree at most half the size of its parent. The recursion depth is therefore at most ⌈log⁡2n⌉\lceil \log_2 n \rceil. Because each level touches every node exactly once (across all parallel subproblems), the total work is O(nlog⁡n)O(n \log n).

Compare this to the naive O(n2)O(n^2) brute force: on a tree with n=106n = 10^6 nodes, brute force requires 101210^{12} operations, while centroid decomposition needs roughly 2×1072 \times 10^7 — a factor of 50,00050{,}000 improvement.

The technique is not a Millennium Problem and is not open: it is a solved, classical algorithm well established in competitive programming and combinatorics since the 1980s. Its status is proven correct and optimal for this class of problems — the O(nlog⁡n)O(n \log n) bound is tight, achieved by a path graph where the centroid always sits in the middle.

Centroid decomposition is closely related to divide and conquer on trees and shares the same philosophy as merge sort: always split at the balance point to bound the recursion depth.

Where It Matters

Any problem of the form "aggregate something over all paths in a tree" becomes tractable with centroid decomposition:

  • Competitive programming: counting paths of length kk, finding the number of paths with sum SS, or answering distance queries between arbitrary node pairs — all classic contest problems solved in O(nlog⁡n)O(n \log n) or O(nlog⁡2n)O(n \log^2 n).
  • Road networks: city maps modeled as trees (spanning trees of planar graphs) admit fast point-to-point distance queries after centroid decomposition preprocessing — used in routing and logistics software.
  • Genome assembly graphs: sequence overlap graphs in bioinformatics are often tree-like; centroid decomposition speeds up repeat-detection passes over long genomic paths.
  • Network monitoring: in tree-topology data-center networks, centroid decomposition underlies efficient broadcast and aggregation schemes that minimize message hops.
  • Offline LCA and distance queries: centroid decomposition is one of the standard tools alongside shortest-path techniques for answering batches of tree-path queries faster than handling each one independently.

The core idea — always recurse on balanced halves — reappears in segment trees, merge sort, and binary search. Centroid decomposition is simply that idea applied to the irregular topology of a tree.

Conclusion

Centroid decomposition is a beautiful example of how the right decomposition collapses an exponential wall. Every path in a tree passes through exactly one centroid in the decomposition hierarchy — so you only need to count the crossing paths at each level, then recurse. The balance guarantee keeps the hierarchy shallow, and the total work stays O(nlog⁡n)O(n \log n).

The next time you face a problem that asks "how many tree paths satisfy property XX?", reach for the centroid: find it in O(n)O(n), count the crossing paths in O(n)O(n) or O(nlog⁡n)O(n \log n), remove it, and recurse. The recursion depth is at most log⁡2n\log_2 n, and your solution runs in a budget any modern machine can meet — even for trees with millions of nodes.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/centroid-decomposition/Content licensed under CC BY-NC 4.0.