Union by Rank or Size

Union by rank or size is a Union-Find optimization that keeps parent trees shallow when merging groups.

It chooses which root should become the parent during union.

Core Idea

Without a rule, repeated unions can create long chains. Union by size attaches the smaller tree under the larger tree. Union by rank attaches the shallower tree under the deeper estimated tree.

Both approaches try to prevent tall structures.

Python Example

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.size = [1] * size
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
 
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
 
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        return True

The smaller group is attached under the larger group.

Common Confusions

Rank is not always the exact height after path compression. It is a guide for merging.

Union by size and union by rank are alternatives. Most implementations need one of them, not both.

When To Use It

Use union by rank or size with path compression for efficient Union-Find operations in connectivity-heavy algorithms.