Union Find (DSU)

Union by Rank

When merging two trees, attach the shorter tree under the taller one. This keeps the tree flat, ensuring find() stays nearly O(1). Track each root's rank (approximate height) to decide.

O(α(n))

O(n)

How It Works

Union by rank controls how two trees are merged so that neither grows needlessly tall. Each root carries a rank, an upper bound on its tree's height. When merging, the root with smaller rank is attached under the root with larger rank, so the combined height does not increase; only when both ranks are equal does the surviving root's rank grow by one. This guarantees a tree of rank r contains at least 2^r nodes, capping heights at O(log n).

Without this heuristic, adversarial union orders can chain nodes into a linked list, making find O(n). With union by rank alone, find costs O(log n); combined with path compression the amortized cost per operation drops to O(alpha(n)), effectively constant. Union by size — attaching the smaller tree under the larger — achieves the same bounds and is often easier to reason about when problems ask for component sizes.

Step-by-Step Visualization

Union by rank keeps trees balanced

Rank[0, 0, 0, 0]

1/3

Code

Java

// See gu-basic for full implementation
// Key idea: when merging two trees
void union(int x, int y) {
  int px = find(x), py = find(y);
  if (rank[px] < rank[py]) parent[px] = py;
  else if (rank[px] > rank[py]) parent[py] = px;
  else { parent[py] = px; rank[px]++; }
}

Tips & Gotchas

1Rank = upper bound on tree height

2Attach shorter tree under taller tree to keep balance

3Rank only increases when merging trees of equal rank

Practice Problems

1Redundant Connection
2Number of Islands II
3Satisfiability of Equality Equations
4The Earliest Moment When Everyone Become Friends

About the Union Find (DSU) Pattern

Track which nodes are in the same connected component. Supports two operations: find(x) returns x's group leader, union(x,y) merges two groups. With path compression and union by rank, both operations are nearly O(1).

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

What is the difference between union by rank and union by size?

Rank tracks an approximate tree height while size tracks node count; both attach the 'smaller' tree beneath the 'larger' and both yield the same asymptotic bounds. Size has a practical bonus: many problems ask for the size of a component, and you get that answer for free from the size array.

Why does rank become inaccurate once path compression is added?

Compression shortens paths without updating rank, so rank ends up only an upper bound on true height rather than the exact value. That is intentional and harmless — the analysis only needs the upper-bound property, and updating heights precisely during compression would be more expensive than it is worth.