Union by Rank in Disjoint Set

Learn Union by Rank in Disjoint Set with practical examples, explanations, best practices, and real-world coding techniques.

What Is Union by Rank?

Union by rank is an optimization technique used with the Disjoint Set Union (DSU), also called the Union-Find data structure. Its purpose is to keep the internal trees as shallow as possible when two disjoint sets are combined.

DSU supports two fundamental operations:

  • Find: determines the representative (root) of an element's set.
  • Union: combines two different sets into one set.

A naive union operation can create unnecessarily tall trees. Union by rank avoids this by attaching the shorter tree below the taller tree whenever two sets are merged.

Why Does Tree Height Matter?

DSU can represent each set as a tree. Every element points toward its parent, and the root of the tree acts as the representative of the set.

Suppose elements are combined in an unfortunate order: 

1
↓
2
↓
3
↓
4
↓
5

Finding the representative of element 5 requires following several parent references. As the tree becomes taller, the cost of find() can increase.

Union by rank attempts to prevent this situation by making the tree structure more balanced.

What Is Rank?

In union by rank, every root stores a value called its rank. Rank is commonly treated as an estimate or upper bound of the tree's height.

Initially, every element forms its own set: 

Element:  1  2  3  4
Parent:   1  2  3  4
Rank:     0  0  0  0

Each element is initially a root with rank 0.

How Union by Rank Works

When performing a union, first find the roots of both elements. Then compare their ranks.

  • If the first root has a smaller rank, attach it below the second root.
  • If the second root has a smaller rank, attach it below the first root.
  • If both ranks are equal, attach one root below the other and increase the resulting root's rank by one.

Case 1: First Tree Has Smaller Rank

Suppose two sets have roots with ranks 1 and 3: 

Tree A                 Tree B

   A                      B
  / \                  / | \
 X   Y                P  Q  R

rank(A) = 1          rank(B) = 3

Since A has the smaller rank, A becomes a child of B: 

        B
      /   |   \
     A    P    Q
    / \         \
   X   Y          R

The larger-rank tree remains the root.

Case 2: Second Tree Has Smaller Rank

The same rule works in reverse. If the second root has a smaller rank, it becomes a child of the first root. 

rank(A) = 4
rank(B) = 2

A becomes the root:

        A
       / \
      B   ...
     / \
    ... ...

This avoids attaching a relatively tall tree below a shorter tree.

Case 3: Both Ranks Are Equal

If two roots have the same rank, either root can become the new root. After combining them, the new root's rank increases by one. 

Before:

Root A (rank 2)       Root B (rank 2)

      A                     B
     / \                   / \
    X   Y                 P   Q

After:

          A
        /   \
       B     X
      / \     \
     P   Q     Y

rank(A) = 3

The exact shape can differ depending on which root is selected, but the important rule is that the rank increases only when two roots with equal rank are merged.

Union by Rank Algorithm

The basic union-by-rank process is:

  1. Find the root of the first element.
  2. Find the root of the second element.
  3. If both roots are the same, the elements are already in the same set.
  4. Compare the ranks of the two roots.
  5. Attach the lower-rank root below the higher-rank root.
  6. If both ranks are equal, attach one root below the other and increase the resulting root's rank.

JavaScript Implementation

The following implementation uses an array for parent references and another array for ranks. Path compression is included in find() so that the two major DSU optimizations work together. 

class DisjointSet {
  constructor(size) {
    this.parent = Array.from(
      { length: size },
      (_, index) => index
    );

    this.rank = new Array(size).fill(0);
  }

  find(value) {
    if (this.parent[value] !== value) {
      this.parent[value] = this.find(this.parent[value]);
    }

    return this.parent[value];
  }

  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]++;
    }

    return true;
  }
}

const dsu = new DisjointSet(6);

dsu.union(0, 1);
dsu.union(2, 3);
dsu.union(1, 2);

console.log(dsu.find(0));
console.log(dsu.find(3));
console.log(dsu.find(4));

Understanding the Parent Array

The parent array stores the parent of every element. A root points to itself. 

parent = [0, 0, 2, 2, 4]

0 ← 1

2 ← 3

4

Here, 0, 2, and 4 are roots because they point to themselves. Elements 1 and 3 belong to the sets represented by roots 0 and 2, respectively.

Why Rank Increases Only When Ranks Are Equal

A common source of confusion is deciding when the rank should change. Rank does not increase every time a union is performed.

If one tree has a larger rank, attaching the smaller tree underneath it does not increase the height of the larger tree. Therefore, its rank remains unchanged.

When both roots have equal rank, attaching one tree below the other can increase the height by one. That is why the resulting root's rank is incremented.

Union by Rank With Path Compression

Union by rank and path compression are two complementary DSU optimizations. Union by rank controls how trees are combined, while path compression makes future find() operations faster.

Consider a chain: 

1
↓
2
↓
3
↓
4
↓
5

After finding the root of 5, path compression can make the nodes on the path point directly to the root: 

    1
  / | \ \
 2  3  4  5

Combining both techniques produces extremely efficient DSU operations for practical algorithmic workloads.

Time Complexity

With union by rank alone, the height of the trees is kept logarithmic, giving a O(log n) upper bound for individual operations in the standard analysis.

When union by rank is combined with path compression, a sequence of m operations on n elements has an amortized complexity of approximately O(m α(n)), where α(n) is the inverse Ackermann function. This function grows so slowly that it is effectively constant for practical input sizes.

Technique Effect Typical Analysis
Naive Union Can create tall trees Can approach O(n) per find
Union by Rank Keeps trees shallow O(log n) per operation upper bound
Path Compression Flattens trees during find Very efficient amortized performance
Rank + Path Compression Controls tree growth and flattens paths O(α(n)) amortized per operation

Union by Rank vs Union by Size

Union by rank is not the only way to keep DSU trees shallow. Another common strategy is union by size.

Union by rank compares the estimated tree height, while union by size compares the number of elements in each set.

Strategy Decision Based On
Union by Rank Rank of the roots
Union by Size Number of elements in each set

Applications of Union by Rank

Union-Find with union by rank is useful whenever an algorithm needs to maintain multiple connected components while repeatedly combining them.

  • Detecting cycles in undirected graphs.
  • Finding connected components.
  • Building minimum spanning trees with Kruskal's algorithm.
  • Managing dynamically connected groups.
  • Grouping elements into disjoint sets.
  • Solving connectivity problems in graph algorithms.

Common Mistakes

  • Updating rank after every union instead of only when the two ranks are equal.
  • Comparing element values instead of comparing root ranks.
  • Calling union without first finding the roots.
  • Attaching one root to a non-root element.
  • Forgetting that path compression and union by rank solve different parts of the optimization problem.
  • Assuming rank always equals the current exact tree height after path compression.

Key Takeaways

  • Union by rank is an optimization for the Disjoint Set Union data structure.
  • It attaches the lower-rank tree below the higher-rank tree.
  • If both ranks are equal, one root becomes the parent and its rank increases by one.
  • Rank helps prevent DSU trees from becoming unnecessarily tall.
  • Union by rank works especially well when combined with path compression.
  • The combination provides nearly constant amortized time for practical DSU operations.

Code Examples 

class DisjointSet {
  constructor(size) {
    this.parent = Array.from(
      { length: size },
      (_, index) => index
    );

    this.rank = new Array(size).fill(0);
  }

  find(value) {
    if (this.parent[value] !== value) {
      this.parent[value] = this.find(this.parent[value]);
    }

    return this.parent[value];
  }

  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]++;
    }

    return true;
  }
}

const dsu = new DisjointSet(6);

dsu.union(0, 1);
dsu.union(2, 3);
dsu.union(1, 2);

console.log(dsu.find(0));
console.log(dsu.find(3));
    
class DisjointSet {
  constructor(size) {
    this.parent = Array.from(
      { length: size },
      (_, index) => index
    );

    this.rank = new Array(size).fill(0);
  }

  find(value) {
    if (this.parent[value] !== value) {
      this.parent[value] = this.find(this.parent[value]);
    }

    return this.parent[value];
  }

  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);

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

    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]++;
    }
  }

  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

const dsu = new DisjointSet(5);

dsu.union(0, 1);
dsu.union(1, 2);
dsu.union(3, 4);

console.log(dsu.connected(0, 2)); // true
console.log(dsu.connected(0, 4)); // false
    
class DisjointSet {
  constructor(size) {
    this.parent = Array.from(
      { length: size },
      (_, index) => index
    );

    this.rank = new Array(size).fill(0);
  }

  find(value) {
    if (this.parent[value] === value) {
      return value;
    }

    return this.find(this.parent[value]);
  }

  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]++;
    }

    return true;
  }
}

const dsu = new DisjointSet(5);

dsu.union(0, 1);
dsu.union(2, 3);
dsu.union(0, 2);

console.log(dsu.parent);
console.log(dsu.rank);

Pro Tip

Think of union by rank as a rule for deciding which root should become the parent: keep the taller-ranked tree as the root and attach the shorter tree beneath it. Combine it with path compression for highly efficient Union-Find operations.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.