Introduction

Path compression is extremely powerful, but it does not make union by rank unnecessary. The two heuristics solve related but different problems: path compression flattens trees during find, while union by rank tries to stop bad tree shapes from forming during union.

What Each Heuristic Actually Does

In a union-find or disjoint-set forest, each set is represented as a tree.

• 'find(x) walks up to the root'
• 'union(x, y) merges two trees'

Path compression improves find by making nodes on the search path point more directly to the root.

1def find(parent, x):
2    if parent[x] != x:
3        parent[x] = find(parent, parent[x])
4    return parent[x]

Union by rank or union by size improves union by attaching the smaller or shallower tree under the larger or taller one.

1def union(parent, rank, a, b):
2    root_a = find(parent, a)
3    root_b = find(parent, b)
4
5    if root_a == root_b:
6        return
7
8    if rank[root_a] < rank[root_b]:
9        parent[root_a] = root_b
10    elif rank[root_a] > rank[root_b]:
11        parent[root_b] = root_a
12    else:
13        parent[root_b] = root_a
14        rank[root_a] += 1

So the heuristics operate at different moments:

• path compression fixes expensive paths after or during searches
• union by rank avoids creating those bad paths in the first place

Why Path Compression Alone Is Not the Whole Story

If you use only path compression, a tree can still become unnecessarily tall before find has a chance to flatten it.

Imagine repeatedly attaching one root under another in an unlucky order. Before enough find operations occur, the structure can still behave worse than necessary.

Union by rank helps because it makes the tree shape more disciplined from the start. Even before path compression runs, the forest is less likely to become badly skewed.

That means union by rank improves the “pre-compression” structure, while path compression improves the “post-access” structure.

An Intuition Example

Suppose you build a long chain of parents:

1 -> 2 -> 3 -> 4 -> 5

A find(1) operation with path compression may flatten it afterward:

11 -> 5
22 -> 5
33 -> 5
44 -> 5
55 -> 5

That is great, but only after the expensive path walk has already happened.

Union by rank tries to prevent such long chains from being created so easily in the first place.

That is the main reason the heuristic still matters.

Why They Work So Well Together

The standard high-performance union-find combines both:

• union by rank or size keeps trees shallow proactively
• path compression flattens them further during queries

Together, they give the classic near-constant amortized performance that makes union-find so useful in algorithms such as:

• Kruskal’s minimum spanning tree
• connected-component tracking
• dynamic connectivity problems

If you omit union by rank, the structure may still perform well in many real workloads, but you lose part of the theoretical and practical protection against bad merge shapes.

Rank Is Not Exact Height

One subtle point is that “rank” does not always mean current exact tree height after path compression has happened.

Once compression starts flattening paths, the stored rank becomes more of an upper-bound heuristic than a precise height measure. That is fine. It still works because union by rank only needs a useful approximation for deciding which root should become the parent.

This is why the heuristic remains valid even though path compression changes the actual shape later.

Could You Skip It in Practice

In some implementations, union by size is preferred over union by rank because it is simple and often just as effective in practice.

But that is not the same as saying “skip the union heuristic entirely.” The real takeaway is:

• path compression is excellent
• some balancing rule during union is still valuable

You may choose rank or size, but keeping a merge heuristic usually makes the structure more robust.

Common Pitfalls

The most common pitfall is assuming path compression instantly fixes every bad tree shape before it causes any cost. It only acts when find is called.

Another mistake is thinking union by rank is redundant because compressed trees look flat afterward. The heuristic matters during construction too.

A third issue is treating rank as if it must always equal the exact current tree height. After path compression, that is no longer the right mental model.

Finally, some developers benchmark only easy operation sequences and conclude that the union heuristic does not matter. Harder sequences and larger workloads show why the combination is standard.

Summary

• Path compression and union by rank solve different parts of the union-find efficiency problem.
• Path compression flattens trees during find.
• Union by rank keeps trees from becoming badly shaped during union.
• Using both together is the standard high-performance approach.
• Even if path compression is strong on its own, a union heuristic still improves robustness and keeps the forest well behaved.