Each preferred path is stored in an auxiliary splay tree where:
- Nodes are ordered by depth in the original tree
- Left subtree = nodes closer to root
- Right subtree = nodes farther from root
Original tree path: root - a - b - c
Splay tree order: root < a < b < c
Splay tree structure (one possibility):
b
/ \
a c
/
root
The splay tree's in-order traversal gives the path from root to deepest node.
Parent pointers: every node has a parent in its auxiliary tree, but the root of each auxiliary tree has a path-parent pointer to the original tree parent (if any).