DSA Interview Prep · Lesson

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.

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 True

The 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))

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

← Back to DSA Interview Prep