What Is Union by Rank? The Union-Find Optimization Explained
- Union by rank attaches the shorter tree under the taller one on every merge, preventing O(n) chain degeneration in union-find.
- Rank is an upper bound on subtree height, starting at 0 and incrementing only when two equal-rank roots merge.
- The equal-rank increment is the most-forgotten rule: when two trees of identical rank merge, the new root's rank goes up by 1.
- O(log n) worst-case follows by induction: a rank-k tree holds at least 2^k nodes, so max rank across n nodes is log₂(n).
- Union by size is an equivalent alternative that tracks node counts instead of heights, with no special equal-case logic to forget.
- Combined with path compression, amortized cost drops to O(α(n)), effectively constant for any realistic n.
Union-find looks deceptively simple. Two operations: find the root of a set, merge two sets. The naive version compiles. It passes small test cases. Then you throw 100,000 nodes at it and watch LeetCode return TLE like it's a personal insult. The culprit is tree degradation. Without any optimization, the tree collapses into a chain, and every find() costs O(n). Union by rank is the fix, bounding find() to O(log n) by enforcing one rule on every merge: always attach the shorter tree under the taller one.
The Problem: Naive Union Builds Chains
The simplest possible union implementation just picks one root and points it at the other. No logic, no comparison, no dignity.
String together five merges on fresh nodes. A bad sequence like union(0,1), union(1,2), union(2,3), union(3,4) produces:
4 → 3 → 2 → 1 → 0
Now find(4) walks four pointers to reach the root. With 10,000 nodes, find() is O(10,000). The data structure is technically correct and no faster than scanning a linked list. You've implemented union-find and accidentally invented a slower version of the thing union-find was invented to replace.
Naive union-find, 11pm, interview tomorrow.
Union by rank prevents this by tracking how tall each subtree is and always making the taller subtree the new root.
What "Rank" Actually Means
Rank is an upper bound on the height of the subtree rooted at a node. Not the exact height. A ceiling. Every node starts with rank 0.
When you merge two sets, compare the ranks of their roots:
rank[a] > rank[b]: attach b's root under a's root. Rank doesn't change.rank[a] < rank[b]: attach a's root under b's root. Rank doesn't change.rank[a] == rank[b]: attach either under the other, then increment the new root's rank by 1.
The equal-rank case is the one candidates forget. When two trees of the same height merge, the combined tree is exactly one level taller, so the new root's rank goes up. Outside that case, rank never increases, because attaching a shorter tree under a taller one doesn't change the taller tree's height.
Forgetting the increment means your rank stagnates at 0 forever. The union "works" in the sense that it connects components, but it does nothing to control height. You're back to chains and you won't know it until you hit a TLE at node 50,000.
A Concrete Walk-Through
Start with five nodes: 0, 1, 2, 3, 4. Every node is its own root. All ranks are 0.
Step 1: union(0, 1)
Both roots have rank 0. Equal ranks, so attach 1 under 0 and increment rank[0].
0 (rank 1)
└── 1
Step 2: union(2, 3)
Both roots have rank 0. Attach 3 under 2, increment rank[2].
0 (rank 1) 2 (rank 1)
└── 1 └── 3
Step 3: union(4, 2)
rank[4] = 0, rank[2] = 1. Node 2's root is taller, so attach 4 under 2. rank[2] stays at 1.
0 (rank 1) 2 (rank 1)
└── 1 ├── 3
└── 4
Step 4: union(0, 2)
rank[0] = 1, rank[2] = 1. Equal. Attach 2 under 0, increment rank[0].
0 (rank 2)
├── 1
└── 2 (rank 1)
├── 3
└── 4
Height is 2. Without rank tracking, the same five nodes in the same bad order could have produced height 4. Every find() that touches these nodes stays fast.
The Implementation
Here's the standard union-find with union by rank and path compression:
class UnionFind: def __init__(self, n: int): self.parent = list(range(n)) self.rank = [0] * n def find(self, x: int) -> int: if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x] def union(self, x: int, y: int) -> bool: rx, ry = self.find(x), self.find(y) if rx == ry: return False # already in the same component if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx # ensure rx is the higher-rank root self.parent[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 return True
The swap guarantees rx is always the root with higher or equal rank, so self.parent[ry] = rx is always correct without duplicating the assignment.
Path compression doesn't break the rank invariant because rank is an upper bound, not exact height. A node can have a rank higher than its actual subtree height after compression. That's fine. The bound still holds. The proof doesn't care about exact values.
Why the Height Stays O(log n)
A tree of rank k always contains at least 2^k nodes. Proof by induction:
- Base case: A tree of rank 0 has exactly one node. 2^0 = 1. Checks out.
- Inductive step: A tree reaches rank k only when two rank-(k-1) trees merge (the equal-rank case). By the inductive hypothesis, each has at least 2^(k-1) nodes. Together: 2^(k-1) + 2^(k-1) = 2^k.
Flip it: if the maximum rank in a structure with n nodes is k, then 2^k ≤ n, so k ≤ log₂(n). Maximum rank, and therefore maximum height, is O(log n). Both find and union cost O(log n) per call.
This is one of those proofs that feels like cheating. You get a logarithmic bound on height just by making sure merges always go the right direction. No black magic required.
Union by Rank vs Union by Size
Both approaches give the same O(log n) bound:
| Approach | What You Track | Equal-case Logic |
|---|---|---|
| Union by rank | Upper bound on height | Increment root rank |
| Union by size | Exact node count | No special case needed |
With union by size, you attach the smaller tree (by node count) under the larger one and sum the sizes. No incrementing logic to forget. Union by rank is what CLRS presents, which is why it shows up more in textbooks and academic settings. In interviews, either works. Pick one, implement it the same way every time, and move on.
Union by Rank and Path Compression: Near-Constant in Practice
Union by rank alone gives O(log n) per operation. Combine it with path compression (every node visited during find() gets rerouted directly to the root) and the amortized cost drops to O(α(n)), where α is the inverse Ackermann function.
α(n) grows so slowly that it is ≤ 4 for any n that could physically be stored on a computer. The universe will end before α(n) hits 5.
The combination of union by rank and path compression is one of the few cases in computer science where the theoretical bound and the practical performance both look like a flat line. Union by rank keeps the tree short to begin with. Path compression makes it flatter over time. Together they are the reason union-find shows up in every serious graph algorithm toolkit.
Why Interviewers Bring It Up
Union-find appears in connected components, cycle detection in undirected graphs, network connectivity, and grouping problems. For interview-sized inputs, a naive implementation gets you the correct answer. At 10^5 or 10^6 nodes, which LeetCode routinely tests, O(n) per operation produces TLE.
This is the part of the interview that separates the two dogs.
The interview signal isn't proving the inverse Ackermann bound on a whiteboard. It's whether you know this optimization exists, can name it, and can implement it from memory. "I'm using union by rank with path compression, which gives O(α(n)) amortized per operation" is the sentence you want to say without hesitating.
Two common mistakes: forgetting the equal-rank increment (rank stagnates at 0, incorrect behavior), and calling find() again when the root is already in hand. Call it once, store it in a variable, reuse it.
If you want to practice explaining these trade-offs out loud under time pressure, SpaceComplexity runs voice-based mock interviews where you reason through optimizations in real time, the exact condition that exposes gaps in your understanding.
For a deeper look at the full data structure, see the union-find algorithm guide and what a disjoint set is. For practice problems, the top union-find problems list covers the most common patterns.
Key Takeaways
- Rank is an upper bound on height, starting at 0 and incrementing only when two equal-rank roots merge.
- The induction proof: rank-k trees contain at least 2^k nodes, so maximum height is O(log n).
- With path compression, amortized cost drops to O(α(n)), effectively constant for any input you'll ever see.
- Union by size is a simpler alternative with no equal-rank logic to track.
- In interviews: know why the optimization matters, and implement it correctly from memory.