Space Complexity

Link-Cut trees use $O(n)$ space:

• $n$ nodes, each with constant fields
• No edge storage needed (edges implicit in parent pointers)
• Lazy flags and aggregates add constant overhead per node

Compare to other structures:

• HLD: $O(n)$ with segment trees included
• Euler tour: $O(n)$ for tour, segment tree adds $O(n)$
• Link-Cut: $O(n)$ total

Link-Cut trees are space-efficient despite their power.