Coding interview: How would you maintain a dynamic forest with a link-cut tree?

Question and scope

You have a dynamic forest whose edges can be added or removed and whose vertices hold integers. Support link(u,v), cut(u,v), path-maximum queries, and path additions. Explain the representation, access, makeroot, lazy tags, correctness, and complexity.

Sleator and Tarjan’s dynamic-tree structure joins two trees and cuts an edge with amortized O(log n) operations. The interview signal is separating represented-tree paths from preferred paths stored in auxiliary splay trees, rather than reciting a template.

What the interviewer is testing

• Know that a link-cut tree maintains a represented forest and auxiliary splay trees for preferred paths.
• Implement isRoot, push, pull, rotations, and splay correctly.
• Explain how access turns the path to the represented root into a preferred path.
• Use a lazy reversal tag for unrooted paths without corrupting propagation order.
• Validate connectivity before link and the exact edge before cut.
• State amortized O(log n) and discuss arrays, recursion depth, and randomized testing.

Questions to clarify first

1. Is the structure guaranteed to remain a forest, or can operations create cycles? Link-cut trees do not solve general dynamic-graph connectivity.
2. Is the path update addition, assignment, or both maximum and minimum? Each requires different aggregate and lazy-tag algebra.
3. Are values on vertices or edges? Represent an edge as a virtual vertex when edge values are needed.
4. Is persistence or concurrency required, or is this a single-threaded online structure?
5. Can input contain duplicate links, missing cuts, or self-loops?

A 30-second answer

I use one auxiliary splay per represented vertex. ch stores splay children and fa is either an auxiliary parent or a represented-path parent. access walks upward, replacing each right child with the already processed path; makeroot accesses and lazily reverses the auxiliary tree. link checks connectivity, makeroots one endpoint, and attaches it. cut makeroots one endpoint, accesses the other, verifies that the left subtree is exactly the edge endpoint, and disconnects it. Push before rotations and pull after updates; operations are amortized O(log n).

Step-by-step deep dive

1. Represent two tree relationships

Auxiliary-splay children describe order on a preferred path. When a node is an auxiliary root, fa is not a splay parent; it is the path parent in the represented tree. Therefore isRoot(x) must test whether x is not either child of fa[x], not merely whether fa[x] is zero.

2. Maintain aggregates and lazy tags

For path maximum, pull(x) combines the value at x with both auxiliary subtrees. A path addition uses an add tag; path reversal swaps children under a rev tag. push must propagate reversal before addition, or otherwise define a proven compositional order.

pull(x): mx[x] = max(value[x], mx[ch[x][0]], mx[ch[x][1]])
applyAdd(x,d): value[x] += d; mx[x] += d; add[x] += d
applyRev(x): swap(ch[x][0], ch[x][1]); rev[x] ^= true

3. Implement access

Set last = 0 and walk from x through fa: splay y, set y’s right child to last, pull y, then set last to y and continue. Finally splay the original x. The path from x to the represented root is now one preferred path whose splay order can answer path aggregates.

4. Implement makeroot

makeroot(x) calls access(x) and applies rev to x. x becomes the represented-tree root, so link(x,y) can join two trees in the intended direction. Do not recursively reverse the represented tree; the auxiliary splay can carry the lazy reversal.

5. Implement link and cut

link(x,y) calls makeroot(x), rejects findroot(y) == x, then sets fa[x] = y. For cut(x,y), call makeroot(x) and access(y). If the edge exists, y’s left child is x and x has no right child; disconnect that child and clear its parent. The structural check prevents cutting a different path edge.

6. Query and update a path

split(x,y) is makeroot(x); access(y), leaving y’s auxiliary splay as the x-to-y path. Read mx[y] for the maximum or apply applyAdd to y for a path update. There is no need to restore preferred paths; the next access will reorganize them.

7. Complexity and tests

Sleator–Tarjan’s analysis gives amortized O(log n) for link, cut, root, and evert, with O(n) space. Cross-check a small implementation against a naive adjacency forest: generate valid links and cuts, compare path maxima and additions, and include singleton trees, repeated makeroot, consecutive accesses, invalid cuts, equal values, and negatives.

High-quality sample answer

I would let fa mean either an auxiliary parent or a represented-path parent and distinguish them with isRoot, rather than treating the represented tree as an ordinary binary tree. Each splay node stores its value, subtree maximum, reversal tag, and addition tag. access exposes a preferred path; makeroot reverses it lazily; split(x,y) makes y’s splay represent the x-to-y path.

link makeroots and rejects already connected endpoints. cut makeroots and accesses, then verifies that y’s left subtree is exactly x before disconnecting it. Push ancestors before rotations and pull after changes. The structure uses amortized O(log n) time and O(n) space; randomized cross-checks against a naive forest cover aggregates, invalid operations, and lazy-tag combinations.

Common mistakes

• Testing fa[x] == 0 for an auxiliary root → a path parent can be nonzero → use the child-based isRoot test.
• Skipping ancestor pushes before rotation → reversal or addition remains hidden → collect ancestors and push in reverse order.
• Cutting without checking the edge → the wrong path edge is removed → verify the left-subtree shape after makeroot/access.
• Linking without a connectivity check → a cycle breaks the forest invariant → compare roots first.
• Treating the post-access splay as the whole represented tree → only one preferred path is exposed → rely on future access operations.
• Testing queries but not updates → lazy-tag bugs stay hidden → compare random path additions with a naive forest.

Follow-up questions and answers

How would you maintain path minimum or XOR?

Replace pull with the required monoid aggregate. XOR is order-insensitive under reversal; a non-commutative aggregate must define path direction and reversal order explicitly.

How do you include edge weights?

Split each edge into a virtual vertex whose value is the edge weight, then use ordinary vertex aggregation. Manage that virtual vertex when linking and cutting.

Why can access replace an old right subtree?

The old subtree remains connected through fa as a represented-path parent; it is merely no longer preferred. Auxiliary-child relationships and path-parent relationships are separate.

Can path assignment be supported?

Add an assignment tag that overwrites older additions, updates value and maximum, and composes with reversal in a defined order. The tag algebra must be explicit and testable.

Why is findroot correct?

After access(x), push tags while following the leftmost child to the leftmost auxiliary node. That node is the represented root; splay it to stabilize later operations.

When should you avoid a link-cut tree?

For a static forest, DFS/Euler tours or heavy-light decomposition are simpler. For general dynamic-graph connectivity, concurrency, or persistence, the maintenance boundary and implementation risk may outweigh the benefit.