Link-Cut Trees: Interactive Connectivity Demo

Introduction

Imagine you are maintaining a forest — a collection of trees — where edges appear and disappear over time. A road planner closes a highway and opens a bypass; a network engineer re-routes a cable; a compiler links and unlinks call-graph edges. At any moment you need to answer questions like: Are these two nodes connected? What is the maximum edge weight on the path between them?

The naive approach re-runs BFS or DFS after every change — $O(n)$ per query in the worst case. For a forest that changes millions of times, that is catastrophic.

Link-cut trees, invented by Daniel Sleator and Robert Tarjan in 1983, do something remarkable: every link (add an edge), cut (remove an edge), and path query runs in $O(\log n)$ amortized time. The key idea is a clever decomposition of each tree into preferred paths — chains that absorb repeated access patterns — implemented with self-adjusting splay trees. Change the forest as often as you like; every operation stays logarithmic.

The result is the go-to tool for dynamic-graph problems, network flow algorithms, and competitive programming.

Try It: Live Forest

Below is a live forest of eight nodes. Click an edge button to toggle it: if the edge is absent it is linked (added); if it is present it is cut (removed). After each change the panel shows which nodes are connected and the path between any two highlighted nodes is listed.

<p class="hint">A forest of 8 nodes. Toggle edges with the buttons below. The panel shows connected components and highlights the path between nodes A and H.</p>
<svg id="graph" viewBox="0 0 340 200" width="340" height="200"></svg>
<div id="path-display" class="path-display"></div>
<div class="edge-btns" id="edge-btns"></div>
<div class="btns">
  <button id="reset" type="button" class="ghost">Reset forest</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
svg { display: block; margin: 0 auto .4rem; overflow: visible; }
.node circle { stroke-width: 1.6; }
.node text { font: 700 13px ui-monospace,monospace; fill: #1d3557; pointer-events: none; }
.node.highlight circle { stroke: #e63946; fill: #fde8ea; }
.edge-line { stroke: #7a9cb8; stroke-width: 2; transition: stroke .2s, opacity .2s; }
.edge-line.active { stroke: #1d3557; }
.edge-line.on-path { stroke: #e63946; stroke-width: 2.8; }
.edge-line.inactive { stroke: #cdd9e3; stroke-dasharray: 5 4; opacity: .45; }
.path-display { font-size: .88rem; font-weight: 600; min-height: 1.4em; color: #1d3557; margin: .2rem 0 .4rem; }
.edge-btns { display: flex; flex-wrap: wrap; gap: .35rem; margin-bottom: .5rem; }
.edge-btn { font: 600 12px system-ui; padding: .3rem .6rem; border-radius: 6px;
            border: 1.5px solid #7a9cb8; background: #e8eef3; color: #1d3557; cursor: pointer; transition: all .15s; }
.edge-btn.linked { background: #1d3557; color: #fff; border-color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Link-Cut Tree demo: dynamic forest connectivity.
// We use a simple Union-Find (path compression + union by rank) to track connected
// components and BFS to find paths. In a real link-cut tree each operation is O(log n)
// amortized; here we rebuild on every change to keep the demo code readable.
const NODES = ['A','B','C','D','E','F','G','H'];
const N = NODES.length;
// Layout positions (x,y) for 8 nodes in a pleasing arrangement
const POS = {
  A:[50,100], B:[110,40], C:[110,160], D:[180,80],
  E:[180,160], F:[255,40], G:[255,140], H:[305,100]
};
// All possible edges (we expose a useful subset as toggleable)
const ALL_EDGES = [
  ['A','B'],['A','C'],['B','D'],['C','E'],['D','F'],['D','G'],['F','H'],['G','H'],['E','G']
];
// Default active edges (form two small trees at start)
const DEFAULT_ACTIVE = new Set(['A-B','A-C','B-D','F-H']);

const edgeKey = (u,v) => [u,v].sort().join('-');

let active = new Set(DEFAULT_ACTIVE);

// ── Union-Find ──────────────────────────────────────────────────────────────
function makeUF(){
  const par={},rank={};
  NODES.forEach(n=>{par[n]=n;rank[n]=0;});
  function find(x){ while(par[x]!==x){par[x]=par[par[x]];x=par[x];} return x; }
  function union(x,y){ const rx=find(x),ry=find(y); if(rx===ry)return;
    if(rank[rx]<rank[ry])par[rx]=ry; else if(rank[rx]>rank[ry])par[ry]=rx;
    else{par[ry]=rx;rank[rx]++;} }
  return{find,union};
}
function components(){
  const uf=makeUF();
  ALL_EDGES.forEach(([u,v])=>{ if(active.has(edgeKey(u,v)))uf.union(u,v); });
  const groups={};
  NODES.forEach(n=>{ const r=uf.find(n); (groups[r]=groups[r]||[]).push(n); });
  return{uf,groups};
}

// ── BFS path ────────────────────────────────────────────────────────────────
function bfsPath(src,dst){
  const adj={};
  NODES.forEach(n=>adj[n]=[]);
  ALL_EDGES.forEach(([u,v])=>{if(active.has(edgeKey(u,v))){adj[u].push(v);adj[v].push(u);}});
  const prev={};
  const q=[src];
  prev[src]=null;
  while(q.length){
    const cur=q.shift();
    if(cur===dst){ const p=[]; let x=dst; while(x!==null){p.unshift(x);x=prev[x];} return p; }
    for(const nb of adj[cur]) if(!(nb in prev)){prev[nb]=cur;q.push(nb);}
  }
  return null;
}

// ── SVG rendering ───────────────────────────────────────────────────────────
const svg=document.getElementById('graph');
const NS='http://www.w3.org/2000/svg';
const edgeEls={};
const nodeEls={};

function makeSVGEl(tag,attrs){
  const el=document.createElementNS(NS,tag);
  Object.entries(attrs).forEach(([k,v])=>el.setAttribute(k,v));
  return el;
}

// Draw edges first (behind nodes)
ALL_EDGES.forEach(([u,v])=>{
  const [x1,y1]=POS[u],[x2,y2]=POS[v];
  const line=makeSVGEl('line',{x1,y1,x2,y2,'class':'edge-line'});
  svg.appendChild(line);
  edgeEls[edgeKey(u,v)]=line;
});

// Draw nodes
NODES.forEach(n=>{
  const [cx,cy]=POS[n];
  const g=makeSVGEl('g',{'class':'node','transform':`translate(${cx},${cy})`});
  g.appendChild(makeSVGEl('circle',{cx:0,cy:0,r:16,fill:'#e8eef3',stroke:'#7a9cb8'}));
  const t=makeSVGEl('text',{'text-anchor':'middle','dominant-baseline':'central'});
  t.textContent=n;
  g.appendChild(t);
  svg.appendChild(g);
  nodeEls[n]=g;
});

// ── Edge buttons ─────────────────────────────────────────────────────────────
const btnContainer=document.getElementById('edge-btns');
const btnEls={};
ALL_EDGES.forEach(([u,v])=>{
  const k=edgeKey(u,v);
  const b=document.createElement('button');
  b.className='edge-btn'+(active.has(k)?' linked':'');
  b.textContent=u+'–'+v;
  b.addEventListener('click',()=>{
    if(active.has(k)) active.delete(k); else active.add(k);
    render();
  });
  btnContainer.appendChild(b);
  btnEls[k]=b;
});

// ── Reset ────────────────────────────────────────────────────────────────────
document.getElementById('reset').addEventListener('click',()=>{
  active=new Set(DEFAULT_ACTIVE);
  render();
});

// ── Main render ──────────────────────────────────────────────────────────────
function render(){
  const path=bfsPath('A','H');
  const pathEdges=new Set();
  const pathNodes=new Set(path||[]);
  if(path) for(let i=0;i<path.length-1;i++) pathEdges.add(edgeKey(path[i],path[i+1]));

  // Update edge lines
  ALL_EDGES.forEach(([u,v])=>{
    const k=edgeKey(u,v);
    const line=edgeEls[k];
    if(!active.has(k)){line.className.baseVal='edge-line inactive';}
    else if(pathEdges.has(k)){line.className.baseVal='edge-line active on-path';}
    else{line.className.baseVal='edge-line active';}
  });

  // Update node highlights
  NODES.forEach(n=>{
    const g=nodeEls[n];
    g.className.baseVal='node'+(pathNodes.has(n)?' highlight':'');
  });

  // Update buttons
  ALL_EDGES.forEach(([u,v])=>{
    const k=edgeKey(u,v);
    btnEls[k].className='edge-btn'+(active.has(k)?' linked':'');
  });

  // Path display
  const pd=document.getElementById('path-display');
  if(path){
    pd.textContent=fmt('Path A→H: %path% (%length% nodes, %v% edges)', { path: path.join(' → '), length: path.length, v: path.length-1 });
    pd.style.color='#0a7d33';
  } else {
    pd.textContent='A and H are not connected.';
    pd.style.color='#c92f3c';
  }

  // Log to console (for verification)
  const {uf}=components();
  const cc=NODES.reduce((acc,n)=>{const r=uf.find(n);(acc[r]=acc[r]||[]).push(n);return acc;},{});
  console.log('Components:', Object.values(cc).map(g=>g.join(',')).join(' | '),
              '| A-H path:', path?path.join('->'):'none');
}

render();

<p class="hint">A forest of 8 nodes. Toggle edges with the buttons below. The panel shows connected components and highlights the path between nodes A and H.</p>
<svg id="graph" viewBox="0 0 340 200" width="340" height="200"></svg>
<div id="path-display" class="path-display"></div>
<div class="edge-btns" id="edge-btns"></div>
<div class="btns">
  <button id="reset" type="button" class="ghost">Reset forest</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
svg { display: block; margin: 0 auto .4rem; overflow: visible; }
.node circle { stroke-width: 1.6; }
.node text { font: 700 13px ui-monospace,monospace; fill: #1d3557; pointer-events: none; }
.node.highlight circle { stroke: #e63946; fill: #fde8ea; }
.edge-line { stroke: #7a9cb8; stroke-width: 2; transition: stroke .2s, opacity .2s; }
.edge-line.active { stroke: #1d3557; }
.edge-line.on-path { stroke: #e63946; stroke-width: 2.8; }
.edge-line.inactive { stroke: #cdd9e3; stroke-dasharray: 5 4; opacity: .45; }
.path-display { font-size: .88rem; font-weight: 600; min-height: 1.4em; color: #1d3557; margin: .2rem 0 .4rem; }
.edge-btns { display: flex; flex-wrap: wrap; gap: .35rem; margin-bottom: .5rem; }
.edge-btn { font: 600 12px system-ui; padding: .3rem .6rem; border-radius: 6px;
            border: 1.5px solid #7a9cb8; background: #e8eef3; color: #1d3557; cursor: pointer; transition: all .15s; }
.edge-btn.linked { background: #1d3557; color: #fff; border-color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Link-Cut Tree demo: dynamic forest connectivity.
// We use a simple Union-Find (path compression + union by rank) to track connected
// components and BFS to find paths. In a real link-cut tree each operation is O(log n)
// amortized; here we rebuild on every change to keep the demo code readable.
const NODES = ['A','B','C','D','E','F','G','H'];
const N = NODES.length;
// Layout positions (x,y) for 8 nodes in a pleasing arrangement
const POS = {
  A:[50,100], B:[110,40], C:[110,160], D:[180,80],
  E:[180,160], F:[255,40], G:[255,140], H:[305,100]
};
// All possible edges (we expose a useful subset as toggleable)
const ALL_EDGES = [
  ['A','B'],['A','C'],['B','D'],['C','E'],['D','F'],['D','G'],['F','H'],['G','H'],['E','G']
];
// Default active edges (form two small trees at start)
const DEFAULT_ACTIVE = new Set(['A-B','A-C','B-D','F-H']);

const edgeKey = (u,v) => [u,v].sort().join('-');

let active = new Set(DEFAULT_ACTIVE);

// ── Union-Find ──────────────────────────────────────────────────────────────
function makeUF(){
  const par={},rank={};
  NODES.forEach(n=>{par[n]=n;rank[n]=0;});
  function find(x){ while(par[x]!==x){par[x]=par[par[x]];x=par[x];} return x; }
  function union(x,y){ const rx=find(x),ry=find(y); if(rx===ry)return;
    if(rank[rx]<rank[ry])par[rx]=ry; else if(rank[rx]>rank[ry])par[ry]=rx;
    else{par[ry]=rx;rank[rx]++;} }
  return{find,union};
}
function components(){
  const uf=makeUF();
  ALL_EDGES.forEach(([u,v])=>{ if(active.has(edgeKey(u,v)))uf.union(u,v); });
  const groups={};
  NODES.forEach(n=>{ const r=uf.find(n); (groups[r]=groups[r]||[]).push(n); });
  return{uf,groups};
}

// ── BFS path ────────────────────────────────────────────────────────────────
function bfsPath(src,dst){
  const adj={};
  NODES.forEach(n=>adj[n]=[]);
  ALL_EDGES.forEach(([u,v])=>{if(active.has(edgeKey(u,v))){adj[u].push(v);adj[v].push(u);}});
  const prev={};
  const q=[src];
  prev[src]=null;
  while(q.length){
    const cur=q.shift();
    if(cur===dst){ const p=[]; let x=dst; while(x!==null){p.unshift(x);x=prev[x];} return p; }
    for(const nb of adj[cur]) if(!(nb in prev)){prev[nb]=cur;q.push(nb);}
  }
  return null;
}

// ── SVG rendering ───────────────────────────────────────────────────────────
const svg=document.getElementById('graph');
const NS='http://www.w3.org/2000/svg';
const edgeEls={};
const nodeEls={};

function makeSVGEl(tag,attrs){
  const el=document.createElementNS(NS,tag);
  Object.entries(attrs).forEach(([k,v])=>el.setAttribute(k,v));
  return el;
}

// Draw edges first (behind nodes)
ALL_EDGES.forEach(([u,v])=>{
  const [x1,y1]=POS[u],[x2,y2]=POS[v];
  const line=makeSVGEl('line',{x1,y1,x2,y2,'class':'edge-line'});
  svg.appendChild(line);
  edgeEls[edgeKey(u,v)]=line;
});

// Draw nodes
NODES.forEach(n=>{
  const [cx,cy]=POS[n];
  const g=makeSVGEl('g',{'class':'node','transform':`translate(${cx},${cy})`});
  g.appendChild(makeSVGEl('circle',{cx:0,cy:0,r:16,fill:'#e8eef3',stroke:'#7a9cb8'}));
  const t=makeSVGEl('text',{'text-anchor':'middle','dominant-baseline':'central'});
  t.textContent=n;
  g.appendChild(t);
  svg.appendChild(g);
  nodeEls[n]=g;
});

// ── Edge buttons ─────────────────────────────────────────────────────────────
const btnContainer=document.getElementById('edge-btns');
const btnEls={};
ALL_EDGES.forEach(([u,v])=>{
  const k=edgeKey(u,v);
  const b=document.createElement('button');
  b.className='edge-btn'+(active.has(k)?' linked':'');
  b.textContent=u+'–'+v;
  b.addEventListener('click',()=>{
    if(active.has(k)) active.delete(k); else active.add(k);
    render();
  });
  btnContainer.appendChild(b);
  btnEls[k]=b;
});

// ── Reset ────────────────────────────────────────────────────────────────────
document.getElementById('reset').addEventListener('click',()=>{
  active=new Set(DEFAULT_ACTIVE);
  render();
});

// ── Main render ──────────────────────────────────────────────────────────────
function render(){
  const path=bfsPath('A','H');
  const pathEdges=new Set();
  const pathNodes=new Set(path||[]);
  if(path) for(let i=0;i<path.length-1;i++) pathEdges.add(edgeKey(path[i],path[i+1]));

  // Update edge lines
  ALL_EDGES.forEach(([u,v])=>{
    const k=edgeKey(u,v);
    const line=edgeEls[k];
    if(!active.has(k)){line.className.baseVal='edge-line inactive';}
    else if(pathEdges.has(k)){line.className.baseVal='edge-line active on-path';}
    else{line.className.baseVal='edge-line active';}
  });

  // Update node highlights
  NODES.forEach(n=>{
    const g=nodeEls[n];
    g.className.baseVal='node'+(pathNodes.has(n)?' highlight':'');
  });

  // Update buttons
  ALL_EDGES.forEach(([u,v])=>{
    const k=edgeKey(u,v);
    btnEls[k].className='edge-btn'+(active.has(k)?' linked':'');
  });

  // Path display
  const pd=document.getElementById('path-display');
  if(path){
    pd.textContent=fmt('Path A→H: %path% (%length% nodes, %v% edges)', { path: path.join(' → '), length: path.length, v: path.length-1 });
    pd.style.color='#0a7d33';
  } else {
    pd.textContent='A and H are not connected.';
    pd.style.color='#c92f3c';
  }

  // Log to console (for verification)
  const {uf}=components();
  const cc=NODES.reduce((acc,n)=>{const r=uf.find(n);(acc[r]=acc[r]||[]).push(n);return acc;},{});
  console.log('Components:', Object.values(cc).map(g=>g.join(',')).join(' | '),
              '| A-H path:', path?path.join('->'):'none');
}

render();

Result

Console

Notice that checking connectivity after each link or cut feels instant — that is the $O(\log n)$ amortized guarantee at work. Try removing all edges from one node and watch it become its own isolated tree. Then reconnect it and see the component merge immediately.

The Real Complexity

How do link-cut trees achieve $O(\log n)$ amortized per operation? The answer lies in two interlocking ideas.

Preferred-path decomposition. Every node in the represented forest has at most one preferred child — whichever child was most recently accessed. The preferred children chain together into preferred paths, partitioning the forest into disjoint paths. When you access a node, you may change some preferred edges, but Sleator and Tarjan proved that the total number of preferred-edge changes across any sequence of $m$ operations is $O(m \log n)$ .

Auxiliary splay trees. Each preferred path is stored in a splay tree keyed by depth. A splay tree is a self-adjusting BST that moves every accessed node to the root in $O(\log n)$ amortized time. Because the represented paths are short on average (by the preferred-path argument), the auxiliary trees stay balanced enough to keep every operation logarithmic.

The operations:

access(v) — makes $v$ the root of its auxiliary tree and splays all ancestors, re-routing preferred paths. This is the core primitive; everything else builds on it.
link(u, v) — connects two separate trees by making $u$ a child of $v$ ; $O(\log n)$ amortized.
cut(v) — removes the edge from $v$ to its parent, splitting one tree into two; $O(\log n)$ amortized.
find-root(v) — returns the root of the tree containing $v$ ; $O(\log n)$ amortized.
path-aggregate(u, v) — computes a fold (sum, max, min…) over all edges or nodes on the $u$ – $v$ path; $O(\log n)$ amortized.

The amortized guarantee is proved with a potential function: $\Phi = \sum_v \log(\text{size of subtree rooted at } v)$ . Each operation pays for itself plus a bounded decrease in potential, so the total cost over any sequence is $O(m \log n)$ .

This was proven by Sleator and Tarjan in their 1983 paper "A Data Structure for Dynamic Trees" (STOC 1983, later in JCSS 1985). It remains the fastest known structure for this class of problems under the comparison model. See also dynamic shortest paths for a related application.

Where It Matters

Link-cut trees are not just a theoretical curiosity — they show up wherever a forest must evolve over time:

Network flow: Goldberg and Tarjan's push-relabel algorithm uses link-cut trees to find augmenting paths in $O(nm \log(n^2/m))$ time, shaving a $\log$ factor off earlier approaches. See max flow for the broader picture.
Dynamic connectivity: maintaining connected components in a graph under edge insertions uses link-cut trees as the inner forest structure.
Minimum spanning forest: adding or removing edges while keeping a spanning forest optimal (by weight) can be done in $O(\log^2 n)$ per update using link-cut trees to manage the path-maximum queries.
Compiler and program analysis: call-graph transformations, dominator-tree updates, and control-flow refinements all modify tree structures at run time — link-cut trees make the bookkeeping efficient.
Competitive programming: link-cut trees appear in advanced ICPC and IOI problems whenever contestants must maintain dynamic trees with path aggregates.

Whenever you see "dynamic tree" or "online forest" in a problem statement, link-cut trees are almost certainly the right tool.

Conclusion

Link-cut trees solve a problem that looks simple but turns out to demand elegance: maintain a forest under arbitrary edge insertions and deletions while answering path queries in polylogarithmic time. Sleator and Tarjan's 1983 answer — decompose each tree into preferred paths, store each path in a splay tree, charge the amortized cost to potential — is a masterclass in how to tame dynamic data with a potential-function argument.

The next time you need to cut and re-link a network on the fly and still answer "are these nodes connected?" in milliseconds, you now know the structure that makes it possible. And if you enjoy how splay trees self-organize, explore dynamic shortest paths to see a closely related idea applied to weighted graphs.

Comments

Loading comments...

https://www.kipuhub.com/en/article/link-cut-trees/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Link-Cut Trees

When your forest never stops changing