Robert Sedgewick says union-find is one of the few algorithms in which the worst-case time complexity is essentially the inverse Ackermann function, which for any imaginable input is at most 4. I love that quote because it sells the destination without explaining the journey, and the journey is what makes the data structure click. The path from the obvious-but-quadratic version of union-find to the version with path compression and union by rank is four implementations, each one a small improvement, and the complexity drops with each step in a way that genuinely surprised me the first time I derived it. This article walks all four, with the actual Java-style code at each step and a one-paragraph proof of why the bound moved.

The complementary article in Category 2 (union-find-explained-with-three-real-problems) is about where union-find earns its keep in production: friend-of-friend graphs, detecting cycles in MST construction, and Kruskal-style edge coalescing. This article is the other half: how the data structure actually works, why path compression matters, and how the four flavors compose. If you have read the applications piece and want to know what is happening inside find(), this is the read.

Implementation 1: parent pointers, naive

The simplest representation: every element has a parent pointer. Two elements are in the same set if they have the same root. The root is its own parent.

class UnionFindNaive {
    int[] parent;

    UnionFindNaive(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;   // each element is its own root
    }

    int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;
    }

    void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) parent[rootX] = rootY;
    }
}

find walks parent pointers until it hits a self-loop. union finds both roots and points one at the other. Both operations are bounded by the depth of the tree.

The failure mode is that adversarial union sequences produce long chains. If you do union(1, 0); union(2, 1); union(3, 2); ...; union(n-1, n-2), you get a linear chain of depth n - 1. Now find(n - 1) walks the entire chain in O(n), and a sequence of n finds is O(n^2). That is the cost: linear per-op worst case, quadratic total.

Naive union-find after the adversarial sequence (depth = n - 1)

n-1 -> n-2 -> n-3 -> ... -> 2 -> 1 -> 0

Nothing in the algorithm prevents this. The fix in the next implementation is to be smarter about which root we point at which.

Implementation 2: union by rank

The idea: when we union two trees, the smaller (shorter) tree should hang under the larger. "Rank" is an upper bound on the depth of a tree; we maintain it explicitly.

class UnionFindRank {
    int[] parent;
    int[] rank;

    UnionFindRank(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;
    }

    void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

The key claim: with union by rank, every tree of rank r has at least 2^r elements. Proof by induction: rank 0 trees have 1 element. The only way a tree's rank increases is when two equal-rank trees are merged, which doubles the element count. So a tree of rank r has at least 2^r elements, which means an n-element tree has rank at most log_2(n). The depth of the tree is bounded by its rank, so find is O(log n) worst case.

Union-by-rank: equal-rank trees stack, lower-rank trees hang

start:    [0]      [1]
union 0,1:    [0]
                |
                1                ranks: 0->1 has rank 1, others rank 0

then union 2,3 then union (root of 0,1) with (root of 2,3):
              0
             /|\
            1 2 3                ranks: 0 has rank 2

find is now O(log n), union is O(log n). Sequence of m operations on n elements: O(m log n). Compared to naive O(m * n), this is a serious win for large inputs.

The rank is technically not the height of the tree once we add path compression in implementation 4; it becomes an upper bound that may overestimate actual depth. The bookkeeping still works because we only use rank to decide which way to attach, and the bound is preserved.

Implementation 3: path compression, no rank

Alternative idea: don't worry about which tree is larger; instead, every time we walk a find chain, flatten it. After find(x), every node from x up to the root points directly at the root.

class UnionFindCompress {
    int[] parent;

    UnionFindCompress(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);   // recursive: returns root, also rewrites parent
        }
        return parent[x];
    }

    void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) parent[rootX] = rootY;
    }
}

The find is recursive and on the way back up the recursion stack, it rewrites every visited node's parent to point directly at the root. Once a node has been touched by any find, its parent is the root, and a future find on it is O(1).

Before find(5)                    After find(5) with path compression

     0                                    0
    /                                  /  |  |  |
   1                                  1  2  3  5
   /
  2
  /
 3
 /
5                                  (all of 1,2,3,5 now point directly to 0)

Without union-by-rank, you can still build up tall trees from adversarial unions. But the very first find on any element in a chain flattens the chain, so the amortised cost over a sequence of operations drops sharply. The worst-case single operation can still be O(n) (the first find after a pathological union sequence), but the amortised cost per operation across m operations is O(log n) (a tighter bound than the per-op O(log n) of rank-only, in the amortised sense). Sedgewick's analysis shows the amortised cost is O(log n) for path compression alone, and the constants are quite good.

The iterative version is also useful in practice because deep recursion can blow stack on large inputs:

int findIterative(int x) {
    int root = x;
    while (parent[root] != root) root = parent[root];
    // second pass: rewrite parents
    while (parent[x] != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

Two passes: find the root, then walk the chain again rewriting pointers. Same big-O behavior; no stack risk.

Implementation 4: union by rank + path compression (the famous one)

Combine both. Rank decides the union direction; path compression flattens during find. The amortised cost per operation drops to O(alpha(n)), where alpha is the inverse Ackermann function. The Ackermann function grows so fast that its inverse, for any input you will ever encounter (n up to the number of atoms in the observable universe), is at most 4. So in practice, every union and find is O(1).

class UnionFindFinal {
    int[] parent;
    int[] rank;

    UnionFindFinal(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

The code is a 5-line addition to Implementation 3 (the rank tracking and the rank-based union direction). The amortised bound is the result of a non-trivial proof by Tarjan, which I will not reproduce here; the proof allocates "credits" to each operation and shows that every operation can pay its own cost plus a small share of the cost of future operations. The end result is that for m operations on n elements, the total work is O(m * alpha(n)), and alpha(n) <= 4 for any practical n.

The theoretical bound is so tight that union-find is sometimes called "essentially constant time per operation" in big-O hand-waving, even though strictly speaking it is super-constant. The constant factor is also tiny: a find on a flattened tree is one or two pointer dereferences. The Kruskal MST algorithm, the connected-components algorithm on a streaming graph, and Boruvka's MST all rely on union-find being fast, and "fast" here means "the constant matters but the asymptotic cost is invisible".

A variant called "path halving" or "path splitting" achieves the same asymptotic bound with a single-pass, non-recursive find. It rewrites every node's parent to its grandparent on the way up, halving the chain length each pass without doing the second-pass walk:

int findHalving(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];   // point at grandparent
        x = parent[x];
    }
    return x;
}

This is what I actually use in production code, because it is iterative, single-pass, and stack-safe. The asymptotic guarantee is the same: O(alpha(n)) amortised per operation.

A side-by-side cost comparison

The gap between row 1 and row 4 is enormous. On n = 1,000,000 and m = 1,000,000 operations: naive does 10^12 work (too slow), full implementation does about 4 * 10^6 work (a single millisecond on modern hardware). That gap is the reason MST construction on a million-edge graph is feasible in real time.

Five questions I keep getting about union-find internals

Why is rank not the actual tree height after path compression? Because path compression flattens trees, so the actual height drops below rank. We don't update rank during compression because doing so would cost extra work and the bound still holds: rank is now an upper bound on height, not equal to it. The amortised analysis works with an upper bound.

Can I use "union by size" instead of "union by rank"? Yes; track the number of elements in each tree and attach the smaller one under the larger. The asymptotic guarantees are the same. Some textbooks use size and some use rank; the choice is mostly stylistic.

Why not just use a HashMap from element to root? Because every union would still need to rewrite the root pointer for every element in the smaller tree, which is O(size) per union. The tree representation pushes that cost into amortised work via path compression and ends up much faster.

Is there a version that supports undo (rollback)? Yes; it is called "persistent union-find" or "union-find with rollback", and it foregoes path compression in favor of a stack of changes. Each operation is O(log n) worst-case (no amortised speedup), but you can rewind the structure to any earlier state. Useful for backtracking algorithms over connectivity.

Does the order of arguments to union matter? Not for correctness. Both union(a, b) and union(b, a) produce the same connectivity. With union by rank, the rank-based decision makes the parent assignment symmetric in the two arguments. Without rank, you might get marginally different tree shapes, but the same set partitions.

What if I need to undo just one operation? Use a single-step rollback variant that records the parent and rank changes for the last union and find and replays them in reverse. This is a more limited form of persistent union-find and is common in interactive algorithms.

The four implementations are the textbook ladder, and walking them in order is the most reliable way I know to internalise why the final version is so cheap. Once you have done it, you will reach for union-find on every connectivity problem in your career, and you will know exactly what the cost is.