Link-Cut Trees

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.

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">{{hint}}</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}}</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; }

// Code not found

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.

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.

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.

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.