Data Structures19 sections · 729 units
Open in Course

Dynamic Tree Problems

Where static fails

Static tree problems: Tree structure is fixed. Use HLD, Euler tour, or tree DP.

Dynamic tree problems: Edges are added/removed. Examples:

  • Network design: connect/disconnect servers
  • Game trees: add/remove moves
  • Dynamic minimum spanning tree

Why Union-Find isn't enough: Union-Find tracks connectivity but can't:

  • Answer path queries (sum, min, max)
  • Support edge deletions (only additions)
  • Find LCA or path length

Link-Cut trees solve all these with O(logn)O(\log n) operations.