Typorithm · medium

Union by Rank

union-find-unionunion-finddisjoint-setunion-by-rankmerge

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Union by Rank

Union-Find

Union finds both roots; if different, attach the smaller-rank tree under the larger, bumping rank only on ties.

Union merges two sets by linking one root under the other.

Attaching the shorter tree beneath the taller keeps the combined tree shallow.

When ranks tie, either root may win, but its rank increases by one to record the new height.

Union by root, not by element.

Shorter tree hangs under taller.

Bump rank only when ranks tie.

union(a, b) {
  const rootA = this.find(a);
  const rootB = this.find(b);
  if (rootA === rootB) {
    return false;
  }

  if (this.rank[rootA] < this.rank[rootB]) {
    this.parent[rootA] = rootB;
  } else if (this.rank[rootA] > this.rank[rootB]) {
    this.parent[rootB] = rootA;
  } else {
    this.parent[rootB] = rootA;
    this.rank[rootA] += 1;
  }

  return true;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Resolve roots

Union operates on set roots, not the raw elements.

const rootA = this.find(a)

2. Already joined

Same root means the elements are already in one set.

if (rootA === rootB) {
    return false;
  }

3. Smaller under larger

Attach the lower-rank tree beneath the higher-rank root.

this.parent[rootA] = rootB

4. Break the tie

On equal ranks, pick a root and bump its rank by one.

this.rank[rootA] += 1

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.