↩ back to Node-Linked Trees

Link-Cut Tree

Two earlier entries already answer "who's connected to whom" over a tree or forest, and both cheat in the same direction: Binary Lifting and Heavy-Light Decomposition build one static structure and answer queries fast forever after — but neither can absorb a single edge being added or removed without a full rebuild. Offline Dynamic Connectivity handles edges changing over time, but only because it's told the entire timeline of changes and queries up front, before doing any work. A Link-Cut Tree drops both crutches: link, cut, and findRoot/connected can arrive in any order, with no advance knowledge of what's coming next, and every one of them still costs only amortized O(log n).

The trick is to stop thinking of the forest as one fixed shape and instead let it be covered, at every moment, by a changing set of vertex-disjoint preferred paths — each one held as a splay tree ordered top-to-bottom by depth, so the usual zig/zig-zig/zig-zag rotations and their amortized argument carry over unchanged, just applied to a path segment instead of a whole ordered set. Everything this page builds — access, link, cut, findRoot — is really one primitive (access) plus three thin callers.

Try it

A 9-node forest, two trees to start: 0 (children 1, 2; then 1→3→4) and 5 (children 6, 7; then 6→8). Click a node to select it as a, click a second to select b, then press a button. Access a exposes the real root-to-a path (traced independently of the algorithm below, straight from the represented-tree parent pointers, so the highlight can't lie about what the algorithm claims to have exposed) — the edges themselves never move, only which path counts as "preferred" changes; compare the drawing before and after. Find Root a answers where a's tree currently ends, highlighting that node. Link a → b only succeeds if a is currently its own tree's root and doesn't already sit inside b's tree (either one would create a cycle). Cut a only succeeds if a isn't already a root. Connected? a, b runs the real algorithm's answer next to an independent parent-pointer walk and reports whether they agree.

Why it works

Two kinds of parent pointer. Every node's array slot holds one parent field doing double duty. If the node is a genuine child inside its own preferred path's splay tree — findable by walking down from that splay tree's root through real left/right child slots — the field is an ordinary aux-tree parent pointer, and rotations update it the usual way. If the node is currently the root of its own splay tree, that same field instead holds a path-parent pointer: the real represented-tree node directly above wherever this preferred path currently ends, invisible to any child array. Telling the two apart is one function, isRoot(x): check whether x is literally recorded as either of its parent's two children. If neither slot names x, its parent field is a path-parent link, and splaying x must stop there rather than rotate across it as though it were a normal tree edge — see the first pitfall for exactly what breaks when this check is weakened to just "does parent exist at all."

access(x) is the one primitive everything else calls. Walk upward from x through real represented-tree ancestors — one path-parent hop at a time, which can leap an entire already-preferred path in a single step, not just one real edge — splaying each one to the top of its own aux tree first, then grafting the piece built up so far onto it as a right child (right, because "everything below where we are" sorts after "here" in depth order) before continuing upward. Reaching a node with no path-parent means the real tree's root has been folded in. One detail is easy to drop and still look right on a first read: the loop's very first move splays x and clears x's own right child — discarding whatever used to be below x on its old preferred path, since access is about to make x the new deepest node on a fresh preferred path, and that old lower segment survives just fine as its own separate path, now hanging off x by a path-parent link instead of a child pointer. The loop's last move is a second splay of x, needed because every earlier splay in the loop was of some ancestor, not x itself — without it, x ends the call buried partway down the newly merged tree instead of sitting at its root, which is exactly the second checked pitfall below.

The three callers. findRoot(x): call access(x), then walk left — never right, since access already guaranteed x has no right child — until there's nowhere left to go; that node is the real represented-tree root, and a final splay of it keeps future calls cheap. link(u, v), valid only when u is currently a real root: access(u) first (a real root always surfaces with an empty left subtree — nothing above it — so this is also a free correctness check), then access(v), then simply set u's parent field to v — a path-parent link, since u is the root of its own aux tree with no parent slot claiming it as a child. cut(x), valid only when x isn't a real root: access(x) leaves everything above x sitting in x's left subtree; detach that subtree's root and clear its parent field entirely (not a path-parent this time — the two pieces are genuinely unrelated now), and clear x's own left slot to match.

Reference implementation

Matches the demo above (the demo also keeps an independent, unrelated parent array purely to draw the forest and to cross-check every answer — no shared code with the two functions below).

function isRoot(x) {
  const p = parent[x];
  if (p === null) return true;
  return left[p] !== x && right[p] !== x;   // not one of p's own children -> parent is a path-parent link
}
function dirOf(x) { return right[parent[x]] === x ? 1 : 0; }
function setChild(p, dir, c) {
  if (dir === 0) left[p] = c; else right[p] = c;
  if (c !== null) parent[c] = p;
}
function rotate(x) {
  const p = parent[x], g = parent[p];
  const d = dirOf(x);
  const wasRoot = isRoot(p);
  const gDir = !wasRoot ? dirOf(p) : -1;
  const c = d === 0 ? right[x] : left[x];
  setChild(p, d, c);
  setChild(x, 1 - d, p);
  parent[x] = g;                     // inherits p's old parent slot -- real edge or path-parent, either way
  if (!wasRoot) setChild(g, gDir, x); // only relink g's *child* slot if p really was one
}
function splay(x) {
  while (!isRoot(x)) {
    const p = parent[x];
    if (!isRoot(p)) {
      if (dirOf(x) === dirOf(p)) rotate(p); else rotate(x);  // zig-zig vs. zig-zag
    }
    rotate(x);
  }
}
function access(x) {
  let last = null;
  for (let y = x; y !== null; y = parent[y]) {
    splay(y);
    right[y] = last;
    if (last !== null) parent[last] = y;
    last = y;
  }
  splay(x);                          // x, not the last y visited -- see Pitfalls
  return x;
}
function findRoot(x) {
  access(x);
  let cur = x;
  while (left[cur] !== null) cur = left[cur];
  splay(cur);
  return cur;
}
function link(u, v) {                // u must currently be a real root
  access(u);
  access(v);
  parent[u] = v;
}
function cut(x) {                    // x must not currently be a real root
  access(x);
  const p = left[x];
  left[x] = null;
  parent[p] = null;
}
function connected(u, v) { return findRoot(u) === findRoot(v); }

Verified against an independent oracle — a plain represented-forest parent array with no restructuring at all, findRoot a straight upward walk — across 2,000 randomized trials of 300 interleaved link/cut/connected calls on 12 nodes and 500 trials of 800 calls on 40 nodes (a million total operations across both runs), 0 mismatches.

Pitfalls

Weakening isRoot to "does this node have a parent at all" — dropping the child-membership check — lets splay rotate straight through a path-parent boundary as if it were an ordinary tree edge, silently merging two things that were never supposed to be one aux tree. Checked directly: build chain 0-1-2 and, separately, chain 3-4-5 (parent[1]=0, parent[2]=1, parent[4]=3, parent[5]=4), access(2), then access(5), then cut(1) — which should split {0} away from {1, 2} while {3, 4, 5} stays untouched. The correct implementation agrees exactly with the independent oracle: connected(0,1)=false, connected(1,2)=true, connected(2,3)=false, connected(3,5)=true. With the weakened isRoot, all four come back false — connected(1,2) and connected(3,5) both flip to wrong answers, on a graph the buggy version never even touched directly with cut.

Dropping access's own final splay(x) — the one after the loop, not the ones inside it — looks harmless, since every ancestor was already splayed on the way up. It isn't: x itself is what every later call trusts to be the aux tree's root; without that last step it can end up buried under whichever ancestor the loop visited last. Checked directly: chain 0-1-2-3, access(3), then cut(1) — correct behavior keeps {1, 2, 3} fully connected to each other while only 0 splits off: connected(0,1)=false, connected(1,2)=true, connected(1,3)=true, connected(2,3)=true. Without the final splay, all four come back false — cut(1) reads left[1] as if 1 were still the aux tree's root, but it isn't anymore, so it detaches the wrong subtree and corrupts the parent field of a node that was never meant to move.

Complexity

Time: access, and everything built on it (findRoot/link/cut/connected), is amortized O(log n) — the same potential-function argument that bounds a lone splay tree's amortized cost, extended to cover the extra work of hopping between preferred paths. Measured, not just derived: on a single worst-case n-node chain (the one input where an unassisted parent-pointer walk would cost O(n) per query), 20,000 random access calls average 11.5, 14.7, and 18.6 rotations at n = 1,000, 4,000, 16,000 — 1.16×, 1.23×, and 1.33× log₂ n at those three sizes respectively, tracking the logarithm rather than growing linearly with n. Space: O(n) — three fields per node (left, right, parent), no per-edge or per-path bookkeeping that grows with forest size or operation count.

Real uses lean on exactly this online generality: maintaining minimum spanning trees under edge insertions and deletions, and dynamic tree DP where subtree/path aggregates need updating as the tree itself is edited — both settings where Offline Dynamic Connectivity's whole-timeline-up-front requirement doesn't fit, because the next edit depends on an answer that hasn't been computed yet.

This site's guide, Choosing a Search Tree, places this entry among the ones that answer a question about a tree's own shape rather than about an ordered set of keys — the tree itself changes shape (via link/cut) instead of just being queried.