The forest is initialized correctly — six self-loops, six independent trees. Each stranger at the conference wears their own name badge. Now you need to merge groups. When Alice meets Bob and they decide to work together, you need to record that connection. That's what union() does.

Mechanically, union(a, b) is straightforward: find the root of a, find the root of b, then make one root point to the other. It's like introducing two group leaders and having one of them agree: “Okay, you're in charge now. People looking for me will be redirected to you.” The follower's badge gets overwritten with the leader's name.

Here's the naive implementation:

union(a: number, b: number) {

  const rootA = this.find(a);

  const rootB = this.find(b);

  if (rootA !== rootB) {

    this.parent[rootB] = rootA;

  }

}

Let me walk through it. The first two lines call find() to chase parent pointers up to the root of each node's tree. This is important — we don't connect a to b directly. We connect their roots. If Alice is in a group led by Dana, and Bob is in a group led by Marcus, then union(Alice, Bob) makes Marcus point to Dana (or vice versa). The two entire groups merge through their leaders.

The if check on line three is a small but critical guard. If rootA === rootB, the two nodes are already in the same group — there's nothing to do. Without this check, you'd create a cycle: a root pointing to itself pointing to itself. It wouldn't crash, but it would silently corrupt the tree structure.

Then the actual merge: this.parent[rootB] = rootA. One assignment. That's it. rootB gives up being a root and becomes a child of rootA. Two trees become one.

But which root becomes the child? This naive version doesn't care. It always makes rootB point to rootA, regardless of tree size, tree depth, or anything else. The first argument wins, always. And this arbitrary choice has consequences.

The first time I implemented Union-Find in an interview, I wrote union() exactly like this — without thinking about tree shape. It passed the sample test cases. The judge accepted it. I moved on feeling clever. What I didn't realize was that the O(n) worst-case was hiding behind small inputs. The test cases had 20 nodes. Try 200,000 and suddenly your “efficient” data structure is slower than a hash set.

Here's the uncomfortable truth about naive union(): it can build a chain. Picture this sequence of calls:

union(0, 1)  // 1 → 0

union(0, 2)  // 2 → 0

union(0, 3)  // 3 → 0

That's fine — a star shape, everything points to 0, maximum depth of 1. But now try:

union(1, 0)  // 0 → 1

union(2, 1)  // 1 → 2

union(3, 2)  // 2 → 3

Now you have a chain: 0 points to 1, 1 points to 2, 2 points to 3. To find the root of node 0, you walk 0 ⟶ 1 ⟶ 2 ⟶ 3. Three hops for four nodes. Extend this to N nodes and you get N-1 hops. The tree has degenerated into a linked list.

And the tree's shape determines how far find() has to walk. Back at the conference, imagine the groups have gotten large. You tap someone on the shoulder: “Who's your group leader?” They say, “I don't know, ask the person ahead of me.” You tap that person. Same answer. You walk down a line of people, each one pointing to the next, and the line stretches across the room. You can see the leader at the far end — but you have to tap every single shoulder between here and there.

Imagine being person number 7 in that line. Someone taps you and asks who your leader is. You don't know — all you have is a pointer to person 6. So you tap person 6. They tap person 5. Person 5 taps person 4. The request propagates forward, one person at a time, and you stand there waiting. You can feel the delay. Each tap is a pointer dereference, each pause is a cache miss, and the line just keeps going.

Does shape actually matter in practice? Let's find out. Below you'll build trees with different union orderings and watch find() count its hops.

You felt the chain growing heavier with every hop. What started as a quick lookup — “just follow the pointer” — turned into a trudge across the entire structure. That weight has a name: O(n) per find. And it compounds. If you call find() on every node in a chain of length N, you pay 0 + 1 + 2 + ... + (N-1) = O(n^2) total hops. Quadratic cost for a data structure that's supposed to be fast.

Here's the naive find() — a while-loop that chases parent pointers to the root:

find(x: number): number {

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

    x = this.parent[x];

  }

  return x;

}

Let me trace through it step by step. We start with some node x. The condition this.parent[x] !== x asks: “Does this node point to itself?” If not, we haven't reached the root yet. The body x = this.parent[x] follows the pointer one level up — one hop. Then we check again. Each iteration is one hop up the tree. When we finally land on a node where parent[x] === x, that's the self-loop — the root — and we return it.

This is clean and correct. The problem isn't the code. The problem is what the code has to traverse.

In a balanced tree — one where each level fans out broadly — the path from any node to the root is short. Maybe two or three hops. Think of a shallow, bushy tree where every node is close to the top. The conference analogy: everyone either knows the leader personally or knows someone who does. One hop, maybe two, and you're there.

But naive union() doesn't build balanced trees. It builds whatever shape falls out of the union ordering. And the worst case is a chain — a tree with branching factor 1, where each node has exactly one child, and every node hangs off the previous one in a single long line. It's a degenerate tree. Technically still a tree. Structurally identical to a linked list.

The cost scales linearly:

• 4 nodes in a chain: 3 hops maximum
• 8 nodes in a chain: 7 hops maximum
• N nodes in a chain: N - 1 hops maximum

That's O(n) per find(). For a data structure whose entire purpose is answering connectivity queries fast, a linear walk is a serious design flaw. And the frustrating part is that every subsequent call to find() on the same node pays the same price. You walk the chain, get the answer, walk away. Next time, you walk the exact same chain again. Nothing was learned from the trip.

It's like navigating a building with no elevator and no memory. You climb to the 7th floor, get what you need, walk back down. Ten minutes later you need the same thing — so you climb all 7 floors again. And again. The staircase is always there, always the same length, and you never think to install an elevator.

But what if you could? What if find() could install an elevator while climbing the stairs? What if the act of querying could reshape the tree, so the next query is cheaper?

That's the idea behind path compression — and it changes everything.