Path Compression in Union Find in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of find with path compression

What is the output of the following code snippet that uses path compression in Union Find?

DSA Javascript

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) {
      this.parent[rootB] = rootA;
    }
  }
}

const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
console.log(uf.find(2));
console.log(uf.parent);

A

0
[0, 0, 0, 3, 4]

B

1
[0, 0, 1, 3, 4]

C

2
[0, 1, 2, 3, 4]

D

0
[0, 1, 0, 3, 4]

💡 Hint

Remember that path compression updates the parent of nodes to the root during find.

The find method compresses the path by setting the parent of each visited node directly to the root. After union(0,1) and union(1,2), all three nodes 0,1,2 share the same root 0. Calling find(2) returns 0 and updates parent[2] to 0. The parent array becomes [0,0,0,3,4].

🧠 Conceptual

intermediate

Effect of path compression on tree height

Which statement best describes the effect of path compression in Union Find?

A It increases the tree height by adding extra nodes during union operations.

B It flattens the tree by making nodes point directly to the root, reducing future find times.

C It removes nodes from the tree to keep it balanced.

D It delays union operations until find is called.

💡 Hint

Think about how path compression changes the parent links during find.

Path compression makes every node on the path from a node to the root point directly to the root. This flattens the structure, making future find operations faster.

❓ Predict Output

advanced

Parent array after multiple unions and finds

What is the state of the parent array after the following operations with path compression?

DSA Javascript

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, 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) {
      this.parent[rootB] = rootA;
    }
  }
}

const uf = new UnionFind(6);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
uf.union(4, 5);
uf.union(2, 5);
uf.find(5);
console.log(uf.parent);

A [0, 0, 0, 3, 3, 3]

B [0, 1, 2, 3, 4, 5]

C [0, 0, 0, 0, 3, 0]

D [0, 0, 0, 0, 0, 0]

💡 Hint

Trace the unions and remember that find compresses paths.

After unions, nodes 0,1,2 form one set and nodes 3,4,5 another. Then union(2,5) connects these sets with root 0. The find(5) compresses the path, updating parents of 5 and 3 to 0. The parent array becomes [0,0,0,0,3,0].

🔧 Debug

advanced

Identify the bug in path compression implementation

What error will the following code cause when calling uf.find(2)?

DSA Javascript

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }
  find(x) {
    if (this.parent[x] === x) {
      return x;
    }
    this.parent[x] = this.find(this.parent[x]);
  }
  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA !== rootB) {
      this.parent[rootB] = rootA;
    }
  }
}

const uf = new UnionFind(3);
uf.union(0, 1);
uf.union(1, 2);
console.log(uf.find(2));

A undefined

B StackOverflowError

C 3

D 2

💡 Hint

Check if all code paths in find return a value.

The find method returns x only if parent[x] === x. Otherwise, it updates parent[x] but does not return anything, so it returns undefined by default. Thus, uf.find(2) returns undefined.

🧠 Conceptual

expert

Amortized time complexity with path compression

What is the amortized time complexity of find operations in Union Find with path compression and union by rank?

A O(1)

B O(log n)

C O(n)

D O(α(n)) where α is the inverse Ackermann function

💡 Hint

The inverse Ackermann function grows extremely slowly.

With path compression and union by rank, the amortized time per find operation is O(α(n)), where α(n) is the inverse Ackermann function, which is very slow growing and practically constant for all reasonable n.

Practice

1. What is the main purpose of path compression in the Union Find data structure?

easy

A. To speed up the find operation by flattening the tree structure

B. To merge two sets without checking their roots

C. To initialize the parent array with default values

D. To count the number of connected components

Solution

1. Step 1: Understand the role of path compression

   Path compression is used during the find operation to make future queries faster by making nodes point directly to the root.

2. Step 2: Identify the effect on the tree structure

   This flattens the tree, reducing the height and speeding up subsequent find calls.

3. Final Answer:

   To speed up the find operation by flattening the tree structure -> Option A

4. Quick Check:

   Path compression = flatten tree = faster find [OK]

Hint: Path compression flattens trees to speed up find [OK]

Common Mistakes:

• Confusing path compression with union by rank
• Thinking it merges sets without root checks
• Believing it initializes data structures

2. Which of the following is the correct syntax for the find function with path compression in JavaScript?

easy

A. function find(x) { if (parent[x] === x) return x; else return find(parent[x]); }

B. function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; }

C. function find(x) { while (parent[x] !== x) x = parent[x]; return x; }

D. function find(x) { parent[x] = x; return x; }

Solution

1. Step 1: Identify path compression in the code

   function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } updates parent[x] to the root during recursion, which is path compression.

2. Step 2: Compare other options

   function find(x) { while (parent[x] !== x) x = parent[x]; return x; } uses iteration but no path compression. function find(x) { if (parent[x] === x) return x; else return find(parent[x]); } uses recursion but no assignment to parent[x]. function find(x) { parent[x] = x; return x; } resets parent incorrectly.

3. Final Answer:

   function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } -> Option B

4. Quick Check:

   Path compression requires parent update = function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } [OK]

Hint: Look for parent update inside find for path compression [OK]

Common Mistakes:

• Missing parent update for path compression
• Using iteration without compression
• Resetting parent incorrectly

3. Given the following code snippet, what will be the output of console.log(parent) after calling find(3)?

let parent = [0, 0, 1, 2, 4];
function find(x) {
  if (parent[x] !== x) parent[x] = find(parent[x]);
  return parent[x];
}
find(3);
console.log(parent);

medium

A. [0, 0, 0, 0, 4]

B. [0, 0, 1, 2, 4]

C. [0, 0, 1, 1, 4]

D. [0, 1, 1, 2, 4]

Solution

1. Step 1: Trace the find(3) call

   find(3) checks parent[3] = 2, not 3, so calls find(2). find(2) checks parent[2] = 1, not 2, so calls find(1). find(1) checks parent[1] = 0, not 1, so calls find(0). find(0) returns 0 since parent[0] = 0.

2. Step 2: Apply path compression updates

   parent[1] = 0, parent[2] = 0, parent[3] = 0 after recursion. But initial array was [0,0,1,2,4]. After updates, parent becomes [0,0,0,0,4]. However, the code only updates parent[x] during recursion. The first call updates parent[3] = find(2) = 0, parent[2] = find(1) = 0, parent[1] = find(0) = 0. So final parent array is [0,0,0,0,4].

3. Final Answer:

   [0, 0, 0, 0, 4] -> Option A

4. Quick Check:

   Path compression sets parents to root = [0,0,0,0,4] [OK]

Hint: Follow recursion and update parents to root [OK]

Common Mistakes:

• Not updating all parents during recursion
• Confusing parent indices
• Assuming no change after find

4. Identify the bug in the following find function implementing path compression:

function find(x) {
  if (parent[x] === x) return x;
  else find(parent[x]);
}

medium

A. Function should use iteration instead of recursion

B. Incorrect base condition for recursion

C. Parent array is not updated for path compression

D. Missing return statement in the else branch

Solution

1. Step 1: Check the recursive calls and returns

   The else branch calls find(parent[x]) but does not return its result, so the function returns undefined for non-root nodes.

2. Step 2: Confirm missing return causes bug

   Without returning the recursive call, the function fails to return the root, breaking the find operation.

3. Final Answer:

   Missing return statement in the else branch -> Option D

4. Quick Check:

   Recursive calls must return values [OK]

Hint: Always return recursive find calls [OK]

Common Mistakes:

• Forgetting to return recursive call result
• Misunderstanding base case
• Thinking iteration is required

5. You have a Union Find structure with parent = [0, 0, 2, 2, 4] and rank = [0, 1, 0, 0, 0]. After performing union(3, 4) and then find(3), what will be the updated parent array assuming path compression is applied in find?

hard

A. [0, 0, 2, 2, 4]

B. [0, 0, 4, 2, 4]

C. [0, 0, 4, 4, 4]

D. [0, 0, 2, 4, 4]

Solution

1. Step 1: Perform union(3, 4)

   Find roots: find(3) = 2, find(4) = 4. Since rank[2] = 0 and rank[4] = 0, attach 3's root (2) to 4. So parent[2] = 4.

2. Step 2: Perform find(3) with path compression

   find(3) calls find(2), which calls find(4). find(4) returns 4. Path compression sets parent[2] = 4 and parent[3] = parent[2] = 4.

3. Final Answer:

   [0, 0, 4, 4, 4] -> Option C

4. Quick Check:

   Union attaches root, find compresses path [OK]

Hint: Union attaches root; find compresses path to root [OK]

Common Mistakes:

• Not updating parent after union
• Ignoring path compression updates
• Confusing rank usage