Link-Cut trees partition each tree into vertex-disjoint paths called preferred paths. Each node has at most one preferred child.
The path from a node down through preferred children is a preferred path. 1 /|\ 2 3 4 Preferred edges: 1-2, 2-5 /| | Preferred path: 1-2-5 5 6 7 Other paths: 3, 4-7, 6 The preferred child can change. when you access a node, you make the path to it the preferred path.
Each preferred path is stored in a splay tree, ordered by depth (top of path = leftmost in splay tree). Time: . Space: .