Path Compression in Union-Find

Learn Path Compression in Union-Find with practical examples, explanations, best practices, and real-world coding techniques.

What Is Path Compression?

Path compression is an optimization technique used with the Union-Find or Disjoint Set Union (DSU) data structure. It improves the performance of the find operation by changing the parent of every visited node to point directly to the root of its set.

Without path compression, a Union-Find tree can become tall. Every time find searches for the representative of a deeply nested node, it may need to follow several parent references. Path compression flattens this structure so that future searches become much faster.

Why Is Path Compression Needed?

A Union-Find set is represented as a collection of trees. Each element points to a parent, and the root points to itself. 

    0
    |
    1
    |
    2
    |
    3
    |
    4

To execute find(4), the algorithm must follow this path: 

4 → 3 → 2 → 1 → 0

The root is 0, but the structure contains several unnecessary levels. If we repeatedly search for the root of 4, we would repeatedly traverse the same chain.

Path compression solves this by changing the structure during the find operation.

How Path Compression Works

During find(x), the algorithm first follows parent references until it reaches the root. While returning from the recursive calls, each visited node is connected directly to that root.

Before compression: 

    0
    |
    1
    |
    2
    |
    3
    |
    4

After calling find(4) with path compression: 

      0
    / | \ 
   1  2  3
         |
         4

More precisely, every node encountered while finding the root is updated to point directly to 0. The exact visual tree can depend on the original parent relationships, but the important result is that the path becomes much shorter.

The Key Line of Code

Path compression is often implemented with a single important assignment inside the find operation: 

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

The recursive call finds the root, and the result is stored as the new parent of x. This means that after the operation, x points directly to the representative.

Step-by-Step Example

Suppose the parent relationships are: 

parent[0] = 0
parent[1] = 0
parent[2] = 1
parent[3] = 2
parent[4] = 3

This creates the chain: 

4 → 3 → 2 → 1 → 0

Now execute find(4).

  1. 4 is not its own parent, so find the parent of 4.
  2. 3 is not the root, so continue.
  3. 2 is not the root, so continue.
  4. 1 is not the root, so continue.
  5. 0 is its own parent, so 0 is the root.
  6. While returning, the visited nodes are updated to point to 0.

The resulting parent relationships become: 

parent[0] = 0
parent[1] = 0
parent[2] = 0
parent[3] = 0
parent[4] = 0

A future find(4) now reaches the root immediately.

Recursive Implementation

The recursive implementation is concise because the recursion naturally handles both finding the root and updating the path. 

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

  return this.parent[x];
}

The base case is reached when an element is its own parent. That element is the representative of the set.

Path Compression Does Not Change Set Membership

Path compression changes only the internal tree structure. It does not move an element from one set to another.

For example, if 0 is the representative of a set containing 0, 1, 2, 3, 4, path compression does not change that membership. It simply makes the parent relationships more direct.

Path Compression and Union

Path compression is primarily an optimization of the find operation. The union operation benefits because it normally calls find to locate the roots before connecting two sets.

For example: 

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

  if (rootA !== rootB) {
    parent[rootB] = rootA;
  }
}

Because find performs path compression, the trees involved in future union and find operations become increasingly shallow.

Path Compression vs No Path Compression

Aspect Without Path Compression With Path Compression
Tree height Can become large Becomes much smaller
Find operation May traverse a long chain Future searches are much shorter
Implementation Simpler Requires parent updates
Repeated operations Can become expensive Highly efficient

Time Complexity of Path Compression

Path compression dramatically improves the amortized performance of Union-Find. When path compression is combined with union by rank or union by size, a sequence of operations has an amortized complexity of O(α(n)) per operation.

The function α(n) is the inverse Ackermann function. It grows extraordinarily slowly, so for practical input sizes it is effectively a very small constant.

This is why optimized Union-Find is considered extremely efficient for problems involving repeated connectivity and set-merging operations.

Path Compression With Union by Rank

Path compression and union by rank are two separate optimizations that work particularly well together.

  • Path compression: shortens existing paths when Find is performed.
  • Union by rank: prevents unnecessarily tall trees when sets are merged.

Using both techniques keeps the Union-Find forest shallow throughout a large sequence of operations.

Where Path Compression Is Useful

Path compression is useful anywhere Union-Find is used heavily, especially when the same elements are queried repeatedly.

  • Connected component problems
  • Cycle detection in undirected graphs
  • Kruskal's minimum spanning tree algorithm
  • Network connectivity
  • Dynamic grouping problems
  • Grid and island connectivity problems
  • Clustering and component-merging problems

Common Mistakes

  • Forgetting to return the root from the recursive call.
  • Finding the root without assigning it back to parent[x].
  • Confusing path compression with union by rank.
  • Assuming path compression changes which set an element belongs to.
  • Using Union-Find when the problem requires actual paths or distances.

A Complete Example

The following example combines path compression with Union-Find and checks whether several elements belong to the same connected component.

Key Takeaways

  • Path compression is an optimization for the Union-Find Find operation.
  • It makes visited nodes point directly to the set representative.
  • It significantly reduces the height of Union-Find trees.
  • The optimization happens while performing Find.
  • Path compression does not change set membership.
  • It is commonly combined with union by rank or union by size.
  • Optimized Union-Find operations have nearly constant amortized time.

Code Examples 

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

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

    return this.parent[x];
  }

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

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

    this.parent[rootB] = rootA;
    return true;
  }
}

const uf = new UnionFind(6);

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

console.log(uf.find(4)); // 0
console.log(uf.parent);  // Paths are compressed after find(4)
    
class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }

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

    return this.parent[x];
  }

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

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

    this.parent[rootB] = rootA;
    return true;
  }

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

const uf = new UnionFind(7);

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

console.log(uf.connected(0, 3)); // true
console.log(uf.connected(0, 5)); // false

// Running find compresses the path.
console.log(uf.find(3)); // 0

Pro Tip

Path compression is most effective when Union-Find performs many repeated find operations. Combine it with union by rank or union by size to keep the structure shallow and achieve near-constant amortized performance.

🎨 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.