Union-Find Explained: Path Compression and Union by Size

Union-Find — also called a disjoint set union — is one of the few data structures where the naive version and the good version look almost identical on the page and behave completely differently. Two small heuristics, each two or three lines, turn a structure that can degrade to linear time into one whose operations are, for every input you will ever see, effectively constant.

The problem it solves

You have n items and a stream of facts of the form "a and b belong together". At any moment you want to ask: are x and y in the same group? How many groups are there?

Friend circles, connected components in a network that keeps gaining links, pixels of the same region, and — the classic interview use — detecting whether a new edge closes a cycle, which is the heart of Kruskal's minimum spanning tree. You could rerun a graph search after every new fact, at O(V + E) each time. Union-Find answers each question in far less.

The intuition

Each group is a tree, stored as nothing more than a parent array. A root points to itself, and the root is the group's name. Two operations:

• find(x) — follow parent pointers up to the root.
• union(a, b) — find both roots; if they differ, point one root at the other.

The only thing that can go wrong is height. If the trees grow tall, find walks a long path, every time. The two heuristics attack height from both ends.

Path compression fixes tall trees after the fact. A find has just walked the entire path to the root, so it already knows the answer for every node on that path. A second pass points each of them straight at the root. The path you paid to walk once is one hop long for everyone afterwards.

Union by size stops tall trees forming in the first place. When joining two trees, hang the smaller one under the larger root. Only the smaller tree's members get one level deeper — and a node only gets deeper when the tree it belongs to at least doubles in size. A tree can double at most log₂ n times, so no node is ever more than log₂ n levels deep.

Union by size bounds how tall a tree can get. Path compression makes sure you only pay for any height once.

Watch it run

The animation starts from a chain — the worst shape a union sequence can build — and runs one find from the bottom. Watch the second pass: every node on the walked path is re-pointed at the root in one sweep, and the chain becomes a star.

The chip row under the graph is the actual parent array. Watching it change is the best way to convince yourself that "flattening a tree" is just a handful of array writes.

The code

class DSU:
    def __init__(self, n, smart=True):
        self.parent = list(range(n))
        self.size = [1] * n
        self.smart = smart
        self.hops = 0                          # pointer steps taken by find

    def find(self, x):
        root = x
        while self.parent[root] != root:       # pass 1: walk up to the root
            root = self.parent[root]
            self.hops += 1
        if self.smart:
            while self.parent[x] != root:      # pass 2: re-point the path
                self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                       # already together: a cycle edge
        if self.smart and self.size[ra] > self.size[rb]:
            ra, rb = rb, ra                    # hang the smaller tree
        self.parent[ra] = rb
        self.size[rb] += self.size[ra]
        return True

small = DSU(5, smart=False)
for i in range(4):
    small.union(i, i + 1)
print(small.parent)    # [1, 2, 3, 4, 4]   a chain: 0 -> 1 -> 2 -> 3 -> 4
small.smart = True
small.find(0)
print(small.parent)    # [4, 4, 4, 4, 4]   one find flattened it

n = 2000
for smart in (False, True):
    d = DSU(n, smart)
    for i in range(n - 1):
        d.union(i, i + 1)
    for i in range(n):
        d.find(i)
    print(smart, d.hops)
# False 1999000
# True 3996

d = DSU(4)
print([d.union(0, 1), d.union(2, 3), d.union(1, 3), d.union(0, 2)])
# [True, True, True, False]    the last edge closes a cycle

The hop counter tells the story. The same 1,999 unions and 2,000 finds cost almost two million pointer steps without the heuristics — the naive unions built one long chain, and each find walked most of it — and under four thousand with them, about two per element.

The last line is cycle detection. union returns False exactly when both ends already share a root, meaning a path between them existed before this edge. That single boolean is what Kruskal's algorithm checks for every edge.

The two-pass find is iterative on purpose. The recursive one-liner, parent[x] = find(parent[x]), is elegant, but in Python a chain a few thousand long exceeds the default recursion limit before compression has had a chance to help.

The complexity

• Neither heuristic: find is O(n) in the worst case, as the chain shows.
• Union by size alone: O(log n) per find, from the doubling argument.
• Path compression alone: O(log n) amortised per operation.
• Both together: O(α(n)) amortised, where α is the inverse Ackermann function. It grows so slowly that it is at most 4 for any n that fits in the physical universe — which is why the operations are described as effectively constant.

Space is O(n): the parent array and the size array.

Where it goes wrong

• Linking the elements instead of their roots. parent[a] = b merges nothing useful if a is not a root — it detaches a from its own group. Always link find(a) to find(b).
• Skipping the same-root check. Linking a root to itself is harmless, but adding its size to itself corrupts the size array.
• Updating the wrong size. The size lives on the root that remains a root. The absorbed root's size is never read again.
• Counting components wrong. Start the count at n and subtract one for every union that returns True.
• Union by rank versus size. Rank tracks an upper bound on height; size tracks the member count. Both give the same guarantees. Size is easier to explain and doubles as the group-size answer that questions often ask for anyway. The union by size lesson compares the two.

How to say it in an interview

"Each group is a tree in a parent array, and the root names the group. find walks to the root and union links two roots. To keep it fast I use union by size — the smaller tree goes under the larger root, so depth stays logarithmic — and path compression, where find re-points every node it walked straight at the root. Together that makes each operation amortised inverse-Ackermann, effectively constant. For cycle detection, an edge whose endpoints already share a root closes a cycle."

If there is time, mention that the structure only merges; it cannot split a group. When a problem needs deletions, Union-Find is the wrong tool, and saying so is a good sign.