# How Disjoint Set (Union-Find) Path Compression Works in JavaScript Algorithms

> Learn how Disjoint Set path compression optimizes Union-Find algorithms. Understand the technique and its JavaScript implementation details.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: deep-dive
- Published: 2026-02-24

---

**The Disjoint Set implementation in the trekhleb/javascript-algorithms repository does not currently apply path compression, though it implements union-by-rank for tree balancing.**

The Disjoint Set data structure, also known as Union-Find, is essential for efficiently managing partitioned sets and detecting cycles in graphs. While path compression is a standard optimization that flattens the structure during find operations, the JavaScript Algorithms repository by Oleksii Trekhleb takes a different approach. This analysis examines how the current implementation handles root finding and what changes would be required to add path compression.

## Current Implementation Without Path Compression

The repository's Disjoint Set implementation relies on recursive parent traversal without modifying intermediate node pointers. This approach maintains tree structure but misses the amortized time complexity benefits of path compression.

### The getRoot() Method in DisjointSetItem.js

In [`src/data-structures/disjoint-set/DisjointSetItem.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/disjoint-set/DisjointSetItem.js), the `getRoot()` method simply walks up the parent chain recursively:

```javascript
getRoot() {
  return this.isRoot() ? this : this.parent.getRoot();
}

```

This implementation returns the root element by following parent pointers until reaching a node where `isRoot()` returns true. However, it does not reassign the parent pointers of traversed nodes, which means subsequent queries for the same elements will traverse the same path again.

### The find() Method in DisjointSet.js

The `find()` method in [`src/data-structures/disjoint-set/DisjointSet.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/disjoint-set/DisjointSet.js) calls `getRoot()` and returns the root key, but again avoids modifying any intermediate nodes:

```javascript
find(itemValue) {
  const templateDisjointItem = new DisjointSetItem(itemValue, this.keyCallback);
  const requiredDisjointItem = this.items[templateDisjointItem.getKey()];
  if (!requiredDisjointItem) return null;
  return requiredDisjointItem.getRoot().getKey();   // no compression here
}

```

This method locates the item in the internal storage object and retrieves its root identifier without flattening the tree structure.

## How Path Compression Should Be Implemented

To implement path compression in this codebase, the `getRoot()` method would need to mutate each visited node's `parent` property to point directly to the root during the recursive ascent. This optimization ensures that future queries execute in nearly constant time.

The modified implementation would look like this:

```javascript
getRoot() {
  if (this.isRoot()) return this;
  this.parent = this.parent.getRoot(); // path compression
  return this.parent;
}

```

By reassigning `this.parent` to the result of the recursive call, each node along the traversal path updates its parent pointer to the root element. This flattens the tree structure progressively, reducing the depth of nodes accessed frequently.

## Union-by-Rank vs. Path Compression

While the repository does not implement path compression, it does employ **union-by-rank** to maintain tree balance. The `union()` method in [`DisjointSet.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/DisjointSet.js) compares the ranks (tree heights) of two sets and attaches the shorter tree under the taller one.

This strategy prevents the tree from becoming too deep during union operations, providing O(log n) time complexity for find operations. However, combining union-by-rank with path compression would yield the optimal **inverse Ackermann function** amortized complexity, making the structure effectively constant time for all practical purposes.

## Practical Usage Example

Here is how to use the current Disjoint Set implementation from the repository:

```javascript
import DisjointSet from './src/data-structures/disjoint-set/DisjointSet';

// Create a set and add elements
const ds = new DisjointSet();
ds.makeSet('A')
  .makeSet('B')
  .makeSet('C')
  .makeSet('D');

// Union operations (by rank)
ds.union('A', 'B');
ds.union('C', 'D');
ds.union('A', 'C'); // now all are in one set

// Find root (no compression performed)
console.log(ds.find('B')); // → key of the root element (e.g., 'A')

// Check set membership
console.log(ds.inSameSet('A', 'D')); // → true

```

## Summary

- The **Disjoint Set** implementation in `trekhleb/javascript-algorithms` uses recursive parent traversal without path compression.
- The `getRoot()` method in [`DisjointSetItem.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/DisjointSetItem.js) walks the parent chain but does not reassign parent pointers to the root.
- **Union-by-rank** is implemented in [`DisjointSet.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/DisjointSet.js) to maintain balanced trees, providing logarithmic time complexity.
- Path compression could be added by modifying `getRoot()` to update `this.parent` during the recursive ascent, achieving near-constant amortized time complexity.

## Frequently Asked Questions

### Does the trekhleb/javascript-algorithms Disjoint Set use path compression?

No, the current implementation does not use path compression. The `getRoot()` method in [`DisjointSetItem.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/DisjointSetItem.js) recursively traverses parent pointers without modifying them, meaning each find operation traverses the same path every time.

### What optimization does the Disjoint Set use instead of path compression?

The implementation uses **union-by-rank** optimization. When uniting two sets, the `union()` method compares the ranks (heights) of the trees and attaches the shorter tree under the taller one, preventing the structure from becoming too deep.

### How would you add path compression to this implementation?

To add path compression, modify the `getRoot()` method in [`DisjointSetItem.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/DisjointSetItem.js) to reassign the parent pointer during recursion:

```javascript
getRoot() {
  if (this.isRoot()) return this;
  this.parent = this.parent.getRoot(); // compress path
  return this.parent;
}

```

This updates each visited node to point directly to the root, flattening the tree for future operations.

### What is the time complexity of the current implementation?

Without path compression, find operations run in **O(log n)** time due to the union-by-rank balancing. With path compression added, the amortized time complexity becomes effectively **O(α(n))**, where α is the inverse Ackermann function, which is less than 5 for all practical values of n.