The Tall Tax

You learned path compression and felt like you'd solved Union-Find. Every node snaps directly to root. One hop. Done. I remember that feeling. I learned compression and thought, “This is it. The chain problem is solved. Time to move on.” I even wrote a blog post about it. I was wrong.

Here's the thing about path compression that nobody warns you about: it's reactive. It fixes chains after they form. You call find() on a deep node, and compression flattens that path. Beautiful. But the chain had to exist first. You had to pay the tall tax — walking the full chain at least once — before compression could do its work.

What if an adversary controls the order of unions?

1
union(1, 0)  // parent[0] = 1
2
union(2, 1)  // parent[1] = 2
3
union(3, 2)  // parent[2] = 3
4
union(4, 3)  // parent[3] = 4
5
// ...keep going...

Every union appends to the chain. After N unions, find(0) walks N hops. Compression will fix it after the first query — but that first query still costs O(N). And if the adversary keeps building fresh chains in other parts of the forest before you query them, every first-touch query pays full price. Compression doesn't help with chains it hasn't seen yet.

The adversary's weapon is the union() call, not the find(). The chain forms during union, not during find. So the question isn't “how do we fix chains?” — compression answers that. The question is: can we prevent the chain from forming in the first place?

Think about what creates a chain. When you call union(a, b), you pick one root to become the child of the other. In the naive version, the choice is arbitrary — the second root always becomes the child. The adversary exploits this by feeding unions in exactly the order that builds the longest chain. But what if the choice wasn't arbitrary? What if union() looked at the two trees and made an intelligent decision about which root goes on top?

That's the insight you're about to discover. You already have compression to fix chains after the fact. Now you need a strategy to stop them from forming. And the strategy is hiding in a question you haven't asked yet: when two trees merge, which one should be the parent?

The tall tax

Phase: Build unions naively
Perform union(1, 0) — tap either node
01234567

Union by Rank

You've just seen it happen: same 8 nodes, same 7 unions, but the rank-aware version produced a tree of height 3 instead of a chain of height 7. That's not a minor improvement. That's the difference between O(n) and O(log n) worst-case find cost — before you even turn on compression.

Let's name the technique and build it properly.

Union by rank maintains a rank array alongside the parent array. Every node starts with rank[i] = 0. When two trees merge, the root with the lower rank becomes the child. The intuition is simple: attach the shorter tree under the taller one, so the combined tree doesn't get any taller than it needs to.

Here's the full implementation:

1
union(a: number, b: number): void {
2
  const rootA = this.find(a);
3
  const rootB = this.find(b);
4
  if (rootA === rootB) return;
5
6
  if (this.rank[rootA] < this.rank[rootB]) {
7
    this.parent[rootA] = rootB;
8
  } else if (this.rank[rootA] > this.rank[rootB]) {
9
    this.parent[rootB] = rootA;
10
  } else {
11
    this.parent[rootB] = rootA;
12
    this.rank[rootA]++;
13
  }
14
}

Walk through each case:

Case 1: rank[rootA] < rank[rootB] — Tree A is shorter. Attach A under B. The combined tree's height is rank[rootB], unchanged. No cost.

Case 2: rank[rootA] > rank[rootB] — Tree B is shorter. Attach B under A. Again, no height increase.

Case 3: rank[rootA] === rank[rootB] — Both trees are the same height. One has to go under the other. We pick rootA as the winner (the choice is arbitrary), attach rootB under rootA, and increment rank[rootA]. This is the only case where rank increases. And it only increases by 1.

That third case is the key. Height only grows when two equal-height trees merge. Think about what this means: to build a tree of rank k, you need to merge two trees of rank k - 1. To build rank k - 1, you need two trees of rank k - 2. This is exponential growth in the number of nodes required. A tree of rank k must contain at least 2^k nodes. For 8 nodes, the maximum rank is 3 (since 2^3 = 8). For a million nodes, the maximum rank is 20. For all atoms in the universe, the maximum rank is ~260.

rank =0
minimum nodes needed
2^0 =1
1 node1,024 nodes

To build rank 20 (million nodes), you need two rank-19 trees. Each of those needs two rank-18 trees... the doubling makes tall trees almost impossible.

Rank is an upper bound, not exact height. This is the subtlety that trips people up. After path compression flattens a branch, the actual tree height decreases, but rank stays the same. We never decrement rank. Why? Because recomputing exact heights after compression would cost O(n) — we'd lose the benefit we're trying to gain. Rank works as an upper bound: it's always ≥ the actual height, which is good enough for the comparison in union(). The slightly-too-large estimate still prevents pathological chains.

01234567rank=3
rank:3(frozen)
actual height:3

Before compression: rank and height match at 3. Both reflect the same tree shape.

Here's the complete Union-Find with both optimizations:

1
class UnionFind {
2
  parent: number[];
3
  rank: number[];
4
5
  constructor(n: number) {
6
    this.parent = Array.from({length: n}, (_, i) => i);
7
    this.rank = new Array(n).fill(0);
8
  }
9
10
  find(x: number): number {
11
    if (this.parent[x] !== x) {
12
      this.parent[x] = this.find(this.parent[x]);
13
    }
14
    return this.parent[x];
15
  }
16
17
  union(a: number, b: number): void {
18
    const rootA = this.find(a);
19
    const rootB = this.find(b);
20
    if (rootA === rootB) return;
21
    if (this.rank[rootA] < this.rank[rootB])
22
      this.parent[rootA] = rootB;
23
    else if (this.rank[rootA] > this.rank[rootB])
24
      this.parent[rootB] = rootA;
25
    else {
26
      this.parent[rootB] = rootA;
27
      this.rank[rootA]++;
28
    }
29
  }
30
}

With both optimizations active, every find() and union() operation takes amortized O(alpha(n)) time, where alpha is the inverse Ackermann function. This is the nearly-constant function you may have heard of — for any practical input size (even 10^80, the number of atoms in the universe), alpha(n) ≤ 4. The proof by Tarjan is one of the great results in theoretical computer science: two simple optimizations (compression and rank), each easy to implement in a single line, combine to produce a data structure that is essentially optimal.

Path compression fixes chains after they form. Union by rank prevents them from forming. Together, they make Union-Find the backbone of Kruskal's MST algorithm, dynamic connectivity, and the next topic in this module: cycle detection. When you check find(a) === find(b) before calling union(a, b), you're asking: “are these two nodes already connected?” If yes, the edge between them would create a cycle. That simple check is the foundation of one of the most common interview patterns — and it runs in effectively O(1) per query, thanks to the two optimizations you just learned.