Union by Rank and the Inverse Ackermann Bound
Add rank-based union to keep trees flat, and understand why the combined optimisations give O(alpha(n)) amortised — effectively constant.
Union by Rank and the Inverse Ackermann Bound is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Trees Get Tall Without Rank
Plain path compression prevents tall trees after traversals, but during the initial union operations, we can still build a tall tree if we always attach the root of the larger tree under the smaller. Union by rank solves this by tracking the upper bound on tree height (the rank) and always attaching the shallower tree under the deeper one.
The rank is not exactly the height — path compression can reduce height below the rank — but it is an upper bound. By keeping the deeper tree as the new root, we ensure the rank only increases when two equally-ranked trees merge, limiting the maximum rank to O(log n).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # initially all trees have rank 0
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
# Attach lower-rank tree under higher-rank tree
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1 # only increases when ranks are equal
return TrueThe Three Cases of Union by Rank
When merging two components with roots px and py, three cases arise based on their ranks:
- rank[px] > rank[py]: attach py under px — rank of px unchanged
- rank[px] < rank[py]: attach px under py — rank of py unchanged
- rank[px] == rank[py]: attach py under px (or vice versa) — rank of the new root increases by 1
The rank only increments in the equal-rank case. This means rank n requires at least 2^n nodes, so the maximum rank is O(log n). This keeps find paths short even without path compression.
# Illustrating rank behaviour with 8 nodes
dsu_parent = list(range(8))
dsu_rank = [0] * 8
def find(x):
while dsu_parent[x] != x:
x = dsu_parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return
if dsu_rank[px] < dsu_rank[py]:
px, py = py, px
dsu_parent[py] = px
if dsu_rank[px] == dsu_rank[py]:
dsu_rank[px] += 1
# Build balanced tree step by step
union(0,1); union(2,3); union(4,5); union(6,7)
union(0,2); union(4,6)
union(0,4)
print('Ranks:', dsu_rank) # max rank <= log2(8) = 3
print('Root of all:', find(0))Combined Path Compression + Union by Rank
When both path compression and union by rank are used together, the amortised time per operation drops to O(alpha(n)) — the inverse Ackermann function. For any practical input size (up to 2^65536), alpha(n) is at most 4. This is effectively constant time.
Path compression flattens trees bottom-up after traversals, while union by rank prevents trees from growing tall top-down during merges. Together they are complementary: rank bounds the initial depth, and compression eliminates that depth after the first traversal.
class OptimalDSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x): # path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y): # union by rank
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = OptimalDSU(1000)
import random; random.seed(42)
for _ in range(5000):
dsu.union(random.randint(0,999), random.randint(0,999))
print('Max rank reached:', max(dsu.rank)) # stays very smallUnderstanding the Inverse Ackermann Function
The Ackermann function A(m, n) grows extraordinarily fast — faster than any primitive recursive function. Its inverse, alpha(n), is defined as the smallest m such that A(m, m) >= n. Because the Ackermann function grows so rapidly, alpha(n) grows unimaginably slowly.
For n = 10^80 (atoms in the observable universe), alpha(n) is still only 4. This is why DSU with both optimisations is treated as effectively constant time in every practical setting. You will never encounter a real problem large enough for alpha(n) to exceed 5.
# Showing how slowly alpha(n) grows
# alpha(n) = smallest m such that A(m,m) >= n
# A(0,n) = n+1
# A(1,n) = n+2
# A(2,n) = 2n+3
# A(3,n) = 2^(n+3) - 3
# A(4,4) = 2^(2^(2^(2^2))) - 3 which is astronomically large
alpha_thresholds = {
1: 'n=1',
2: 'n up to 3',
3: 'n up to about 2048',
4: 'n up to 10^19728 (far beyond atoms in universe)',
5: 'essentially unreachable in practice',
}
for k, v in alpha_thresholds.items():
print(f'alpha(n)={k}: {v}')
print('\nConclusion: DSU operations are effectively O(1) for all real inputs.')Rank vs Size: Which to Use?
An alternative to union by rank is union by size: always attach the smaller-size tree under the larger-size tree. Both approaches give the same O(log n) height guarantee. Union by size is often easier to reason about because sizes are exact counts, while ranks are upper bounds that may not reflect the true height after compression.
In interviews, either approach is acceptable. Union by size has the added benefit of giving you component sizes for free, which many problems require. Union by rank is slightly more theoretically elegant and matches the original Tarjan proof of the inverse Ackermann bound.
class DSUBySize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.size[px] < self.size[py]:
px, py = py, px # always attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
return True
dsu = DSUBySize(8)
for u, v in [(0,1),(2,3),(0,2),(4,5),(6,7),(4,6),(0,4)]:
dsu.union(u, v)
print('Size of giant component:', dsu.size[dsu.find(0)])Proof Sketch: Why Rank Stays at O(log n)
We can prove by induction that a DSU tree with rank r contains at least 2^r nodes. Base case: rank 0 means a single node (2^0 = 1). Inductive step: rank r only increases when two equal-rank-r-1 trees merge. By the inductive hypothesis, each subtree has at least 2^(r-1) nodes, so the merged tree has at least 2 × 2^(r-1) = 2^r nodes.
Since a tree of rank r has at least 2^r nodes, and we have n total nodes, the maximum rank is at most log₂(n). This means find without path compression takes O(log n) time, and with path compression the amortised cost drops much further.
# Verify the 2^rank lower bound empirically
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]: self.rank[px] += 1
n = 32
dsu = DSU(n)
for i in range(n - 1): dsu.union(i, i + 1)
for root in range(n):
if dsu.find(root) == root:
r = dsu.rank[root]
print(f'Root {root}: rank={r}, size={dsu.size[root]}, 2^rank={2**r}')DSU Template for Competitive Programming
In competitive programming and interviews, you want a battle-tested DSU template that is short, correct, and handles all edge cases. The template below uses path halving (one-pass compression) combined with union by size — a combination that is easy to type quickly and avoids recursion entirely.
Always initialise parent[i] = i and size[i] = 1. Remember that after find, the root's size reflects the whole component. Never use size[x] directly — always call size[find(x)].
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.sz = [1] * n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]] # path halving
x = self.p[x]
return x
def union(self, x, y):
x, y = self.find(x), self.find(y)
if x == y: return False
if self.sz[x] < self.sz[y]: x, y = y, x
self.p[y] = x
self.sz[x] += self.sz[y]
return True
def same(self, x, y): return self.find(x) == self.find(y)
def size(self, x): return self.sz[self.find(x)]
# Usage
dsu = DSU(10)
dsu.union(0, 5)
dsu.union(5, 9)
print(dsu.same(0, 9)) # True
print(dsu.size(0)) # 3When DSU Is Not Enough
DSU supports merging sets but does not support splitting a set back into two. If a problem requires both joining and separating groups, you need a different structure (like a link-cut tree). DSU also does not natively store the elements of each group — you need an additional adjacency list or dictionary for that.
Additionally, standard DSU does not support weighted edges without modification (weighted DSU is a more advanced variant). For problems like cheapest path between connected nodes, Dijkstra or BFS is more appropriate. Recognising DSU's scope prevents misapplying it.
# DSU is perfect for: connected-components, cycle detection,
# Kruskal's MST, accounts-merge, number-of-provinces
# DSU is NOT suitable for:
# - Splitting/removing edges from a group
# - Finding the actual path between two nodes
# - Storing all members of a group efficiently
# - Directed graphs (without modification)
# Example of storing group members alongside DSU
from collections import defaultdict
class DSUWithMembers:
def __init__(self, n):
self.p = list(range(n))
self.members = defaultdict(set)
for i in range(n): self.members[i].add(i)
def find(self, x):
while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
self.members[px] |= self.members[py]
del self.members[py]
self.p[py] = pxComparing DSU to BFS/DFS for Connectivity
Both BFS/DFS and DSU solve static connectivity queries, but they have different strengths. BFS/DFS runs in O(V + E) and can find the actual path between nodes. DSU answers many connectivity queries over incrementally growing edge sets with near-O(1) per query — ideal for online algorithms where edges arrive one at a time.
If you receive all edges upfront and only need connectivity, either works. If edges arrive dynamically and you need to answer connectivity queries between each new edge, DSU is the clear winner. For problems that also need the shortest path, stick with BFS.
# Comparing DSU vs BFS for 1000 nodes, 2000 edges
# After all edges given => BFS works fine
# But with online edge arrival + interleaved queries => DSU shines
from collections import deque
def bfs_connected(graph, src, dst, n):
visited = set([src])
q = deque([src])
while q:
node = q.popleft()
if node == dst: return True
for nb in graph.get(node, []):
if nb not in visited:
visited.add(nb); q.append(nb)
return False
# DSU for same query:
# dsu.same(src, dst) -- O(alpha(n)) amortised
# BFS for same query:
# O(V + E) every time -- not suitable for repeated queries
print('DSU is preferred for repeated connectivity queries.')
print('BFS/DFS is preferred when you also need the actual path.')Practice: Minimum Spanning Tree with DSU
Kruskal's algorithm for minimum spanning tree directly uses DSU. Sort all edges by weight, then greedily add each edge if its endpoints are in different components (no cycle). DSU provides the cycle check in near-O(1). The result is an MST of n-1 edges.
This is a classic demonstration of DSU's power: it converts an O(E × V) naive cycle check into an O(E × alpha(n)) process. With E log E sorting, Kruskal's total time is O(E log E), and DSU operations are so fast they are negligible compared to the sort.
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
parent = list(range(n))
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
mst_weight = 0
mst_edges = []
for u, v, w in edges:
if union(u, v):
mst_weight += w
mst_edges.append((u, v, w))
return mst_weight, mst_edges
edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,5)]
w, e = kruskal(4, edges)
print('MST weight:', w) # 6: edges (1,2,1)+(1,3,2)+(0,2,3)
print('MST edges:', e)DSU with Rollback: Offline Connectivity
Standard DSU does not support undo operations. However, DSU with rollback (also called DSU with history) does: instead of path compression (which is hard to undo), use only union by rank, and record each union in a stack. To roll back, pop from the stack and restore parent and rank. This enables solving offline dynamic connectivity problems where edges may be added and removed.
While this is an advanced variant rarely seen in standard interviews, it demonstrates that union by rank is the crucial invariant — not path compression. Without path compression, each find is O(log n), and with rollback the stack operations are O(1), giving O(log n) per operation overall instead of O(alpha(n)).
class DSUWithRollback:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.history = [] # stack of (node, old_parent, node2, old_rank)
def find(self, x): # NO path compression (cannot undo)
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rank[px] < self.rank[py]: px, py = py, px
# Record state before modifying
self.history.append((py, self.parent[py], px, self.rank[px]))
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
return True
def rollback(self):
py, old_par_py, px, old_rank_px = self.history.pop()
self.parent[py] = old_par_py
self.rank[px] = old_rank_px
dsu = DSUWithRollback(5)
dsu.union(0, 1); dsu.union(1, 2)
print('0 and 2 connected:', dsu.find(0) == dsu.find(2)) # True
dsu.rollback()
print('After rollback:', dsu.find(0) == dsu.find(2)) # FalseQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: union by rank always attaches the shallower tree under the deeper tree, rank increases only when two equal-rank trees merge, keeping tree height at O(log n), and combining path compression with union by rank achieves O(alpha(n)) amortised — effectively constant time. Next up we apply the full optimal DSU to redundant connection and cycle detection in graphs.
Frequently asked questions
Is the “Union by Rank and the Inverse Ackermann Bound” lesson free?
Yes — the full text of “Union by Rank and the Inverse Ackermann Bound” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Union by Rank and the Inverse Ackermann Bound”?
Add rank-based union to keep trees flat, and understand why the combined optimisations give O(alpha(n)) amortised — effectively constant. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Union by Rank and the Inverse Ackermann Bound” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- DSU with Path Compression
- Union by Rank and the Inverse Ackermann Bound
- Redundant Connection and Cycle Detection
- Accounts Merge and Connected Components