Link-Cut Tree

The Problem: Trees That Change Shape

A rooted tree is a familiar structure: a hierarchy where every node except the root has exactly one parent, and the tree defines a natural notion of ancestry, depth, and paths between nodes. Many algorithms rely on trees that are built once and then queried repeatedly, such as a binary search tree used for lookups or a segment tree used for range queries. But a large class of problems needs something different: a forest of trees that is repeatedly restructured over time. Two operations define this need. A link operation attaches the root of one tree as a child of a node in another tree, merging two trees into one. A cut operation removes the edge between a node and its parent, splitting one tree into two. Between these updates, we still want to answer questions such as: what is the root of this node's tree right now, are two nodes in the same tree, or what is the minimum or maximum edge weight on the path connecting two nodes. If we used an ordinary tree representation with explicit parent pointers and, say, a depth array or ancestor tables, a single cut deep in a large tree could force us to recompute depths and ancestor information for an entire subtree, costing linear time in the worst case. Repeating that across many operations quickly becomes unacceptable for large dynamic systems. The link-cut tree was designed precisely to avoid this: it guarantees that link, cut, and path queries all run in amortized O(log n) time, no matter how the forest is reshaped, by cleverly bounding the total work done across a sequence of operations rather than bounding every single operation in isolation.

Preferred-Path Decomposition

The central idea behind the link-cut tree is to decompose each tree in the forest into a set of vertex-disjoint preferred paths, sometimes called heavy paths in related structures. At any given moment, every node has at most one preferred child among its children in the represented tree, and the edge to that child is called a preferred edge. A maximal chain of preferred edges forms a preferred path. This partition is not fixed forever; it changes as the structure is accessed, based on which routes through the forest have been recently traveled. Crucially, each preferred path is stored not as a plain linked list but as an auxiliary splay tree, with nodes ordered by their depth in the original represented tree, so the leftmost node in the splay tree is the shallowest (closest to the root of that path) and the rightmost is the deepest. Edges that are not preferred, called dashed edges, connect the root of one auxiliary splay tree to a specific node in another auxiliary splay tree, effectively linking the path structures into a hierarchy of paths. This two-level design is what makes the whole thing work: within a preferred path, splay trees give efficient amortized access to any node by depth, and the dashed edges let the structure represent an arbitrarily branching tree using only a collection of simple paths. The number of preferred paths from any node up to the root of its tree is bounded logarithmically thanks to the same accounting argument used in heavy-path decomposition, which is the seed of the amortized time bound for the whole structure.

The Access Operation and Splicing

Nearly every link-cut tree operation is built on top of a single primitive called access. Given a node, access walks from that node up to the root of its represented tree, and along the way it makes every edge on that path a preferred edge, effectively promoting the entire path from the node to the root into one single preferred path. It does this by repeatedly splaying the node to the root of its own auxiliary splay tree, then following the dashed edge to the parent path, splaying there too, and switching which child was previously preferred so that the path just traversed becomes preferred instead. This process is often called splicing: each step splices the auxiliary splay tree of the current path onto the auxiliary splay tree of the next path up, using a splay operation to reattach and rebalance. After access completes, the accessed node is the deepest node in a single splay tree that spans the entire root-to-node path, and it has been splayed to the root of that auxiliary tree, giving direct access to it and, by extension, to information about the whole path. Because splay trees guarantee amortized logarithmic time per operation via the well-known potential function argument, and because the number of distinct preferred paths crossed during any access is itself bounded logarithmically in an amortized sense, the entire access operation runs in amortized O(log n) time. Every other link-cut tree operation, including link, cut, find-root, and path aggregate queries such as minimum edge weight, is expressed as a small constant number of accesses plus O(1) extra pointer manipulation, which is why the whole structure inherits the same logarithmic bound.

Link, Cut, and Path Queries in Practice

With access as the workhorse, the other operations become short and elegant. To link two trees by making node u a child of node v, we first access u to bring it to the root of its represented tree with no preferred parent, then attach it as a new preferred child beneath v after accessing v. To cut the edge above node u, we access u, which brings the entire path from u to its tree's root into a single splay tree with u at the deepest position; because splay-tree order corresponds to depth, u's left subtree in that splay tree corresponds to all of u's proper ancestors, so cutting is simply a matter of detaching that left subtree, an O(1) pointer operation once the splay tree is arranged. To answer a path query, such as the minimum edge weight between two nodes, we typically access one node to make it the root of the whole forest (a technique often called make-root or evert, achieved with a lazy orientation-reversal flag), then access the second node, and the resulting splay tree spans exactly the path between them, letting us read off an aggregate value maintained incrementally at each splay-tree node, similar to how a segment tree maintains range aggregates. These building blocks make link-cut trees the tool of choice for algorithms such as maintaining a dynamic minimum spanning forest under edge insertions and deletions, speeding up network flow algorithms like the dynamic trees enhancement of Dinic's algorithm, and supporting fully dynamic connectivity queries where edges are added and removed over a long sequence of operations.

Contrast With Static Trees

The value of a link-cut tree becomes obvious when you compare it against a static tree representation used for the same dynamic workload. A static tree is typically built once, perhaps with precomputed ancestor tables for binary lifting, an Euler tour for lowest-common-ancestor queries, or a heavy-light decomposition mapped onto a segment tree. All of these techniques are excellent when the tree's shape never changes, offering fast queries after a one-time preprocessing cost. But the moment you need to cut an edge deep inside the tree or link in a new subtree, that precomputed information becomes stale. An Euler tour must be rebuilt, ancestor tables must be recomputed for potentially every descendant of the changed subtree, and a heavy-light decomposition may need entire chains reassigned, all of which can cost O(n) time for a single update in the worst case. If updates are frequent and interleaved with queries, as they are in dynamic connectivity problems or online minimum spanning forest maintenance, this static approach degrades to unacceptable total running time over a long sequence of operations. The link-cut tree sidesteps this entirely by never committing to a fixed decomposition: its preferred paths are allowed to shift with every access, and the cost of that shifting is paid for by the amortized analysis of the underlying splay trees, so that even a worst-case adversarial sequence of links, cuts, and queries still totals only O(m log n) time for m operations on a forest with n nodes. This is the essential trade-off the lab is meant to make visible: a static structure buys simplicity and fast queries only as long as nothing changes, while a link-cut tree buys resilience to constant restructuring at the cost of a more intricate internal representation.

Frequently asked questions

Try it live

Everything above runs in your browser — open Link-Cut Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.