In the last lesson, you built a chain and felt find() slow down with every hop. A chain of 8 nodes costs 7 hops — and that cost hits every single query on any node in the chain. But the worst part isn't the cost itself. It's the repetition.

You call find(7) and walk 7 hops to the root. You arrive, get your answer, and return. Then you call find(7) again. Same 7 hops. Same path. Same root at the end. Nothing has changed. The tree hasn't learned anything from your visit. It's like calling a company's help line, getting transferred through 6 departments — “let me connect you to billing,” “actually you need fulfillment,” “hold on, I'll transfer you to operations” — and finally reaching the one person who can help. You get your answer. Great.

Then you hang up without saving their direct number.

Next week, same question. You call the main line. “Let me connect you to billing.” “Actually you need fulfillment.” Six transfers. Again. The same six people, in the same order, doing the same redirecting, and you sitting on hold through every single one. If only you had saved that direct number the first time. If only the phone system had noticed you made this exact trip already and just... remembered.

That's the situation naive find() is in. Here's the code you've been using:

find(x: number): number {

  while (this.parent[x] !== x) {

    x = this.parent[x];

  }

  return x;

}

It walks the chain honestly, one hop at a time, and returns the root. But it leaves the tree exactly as it found it. Every pointer still points to the same intermediate parent. Every future traversal pays the same price.

I remember reading about path compression for the first time and thinking, “You can't just... rewrite the tree during a query. That's a read operation. Reads don't modify things. That breaks everything.” Except it doesn't. It's one of the most elegant tricks in all of computer science. The insight is that find() already knows the answer for every node it visits along the way. When you walk from node 7 to node 6 to node 5 all the way to the root — at that moment, you know the root of node 7, and the root of node 6, and the root of node 5. They're all the same root. So why not save that information? Why not rewire each node to point directly to the root as you return?

That's path compression. During a read operation, you rewrite the tree to make future reads faster. You're not changing the answer — every node still belongs to the same group, still has the same root. You're just removing the middlemen. You're saving the direct number for every department you got transferred through, not just the final one.

One added line turns O(n) into nearly O(1). Can you find it?

The chain became a star in front of your eyes. Nodes that were 6 hops from the root are now 1 hop away. That dramatic restructuring — a chain collapsing into a flat fan — is path compression in action. You saved the direct number. Not just for yourself, but for every node you passed through on the way.

Let me build the compressed find() step by step.

First, the signature — same as before:

find(x: number): number {

This takes a node and returns its root. From the outside, the behavior is identical to the naive version. Same input, same output. The difference is entirely internal — what the function does to the tree along the way.

Next, the base case:

  if (this.parent[x] !== x) {

If parent[x] === x, we've hit the self-loop — this node IS the root. Return it. Nothing to compress. But if parent[x] !== x, we're somewhere in the middle of a chain, and this is where the magic happens.

The recursive call with compression:

    this.parent[x] = this.find(this.parent[x]);

  }

  return this.parent[x];

Read that line carefully: this.parent[x] = this.find(this.parent[x]). The right side, this.find(this.parent[x]), recurses upward — it follows the chain all the way to the root and returns the root's identity. The left side, this.parent[x] =, rewrites this node's parent pointer to point directly at that root. The recursion descends to the root, and then on the way back up through the call stack, every visited node gets its parent pointer overwritten.

Here's the complete function:

find(x: number): number {

  if (this.parent[x] !== x) {

    this.parent[x] = this.find(this.parent[x]);

  }

  return this.parent[x];

}

Same traversal as the naive version — you still visit every node on the path. But now, as the recursion unwinds, each node's parent gets set to the root. A chain of 7 becomes 7 direct children of the root. The next call to find() on any of those nodes? One hop. Done.

If your brain just went “wait — this modifies the tree during a query?” — good. That tension is real. Most data structures treat reads as pure operations. A get() on a hash map doesn't reorganize the buckets. A search() on a BST doesn't rebalance the tree. Reads observe; they don't change. Union-Find breaks that rule, and it's better for it. The modification doesn't change the observable result — the root is still the root, the groups are still the groups — but it changes the performance of every future query.

There's a subtlety worth naming: compression only flattens the path you actually walked. If the tree has multiple branches, nodes on other branches are untouched. They're still however many hops away they were before. They'll get their own shortcuts the first time someone queries them. Compression is lazy and local. It doesn't try to fix the whole tree at once. It fixes what it touches, when it touches it. And that's exactly why it's cheap — you're not paying for a global restructuring. You're amortizing the cost of future queries over the queries that trigger the restructuring.

This property — “fix the path you're already walking” — is what makes path compression feel like getting something for free. You were going to walk the chain anyway to answer the query. The only added cost is writing back the root to each node as you return. One extra assignment per hop. And in exchange, you've permanently flattened that path. It's one of those rare optimizations where the bookkeeping is almost invisible but the payoff is enormous.

Combined with union-by-rank (the next lesson), this gives amortized O(alpha(n)) per operation, where alpha is the inverse Ackermann function. For any practical input size — even if n is the number of atoms in the observable universe — alpha(n) is at most 4. That's not O(log n). That's not O(log log n). It's a function that's technically not constant but is so close to constant that the distinction is purely academic. Effectively free. And you get it by breaking the rule that reads don't write.

Constructor wired. find() optimized. One piece remains: when two trees merge, which root becomes the child? If you attach the tall tree under the short one, you've rebuilt a chain. The smarter choice keeps the forest shallow — and that's union by rank.