Path Compression in Union Find in DSA Javascript - Build from Scratch

Path Compression in Union Find

📖 Scenario: Imagine you are managing a social network where people form friend groups. You want to quickly find out if two people are in the same friend group and efficiently merge groups when new friendships form.

🎯 Goal: You will build a Union Find data structure with path compression to efficiently find the leader (representative) of each friend group and merge groups.

📋 What You'll Learn

Create an array called parent representing each person's parent in the friend group.

Create a variable called n for the total number of people.

Write a function called find that uses path compression to find the leader of a person.

Write a function called union that merges two friend groups.

Print the parent array after some unions to show path compression effect.

💡 Why This Matters

🌍 Real World

Union Find with path compression is used in social networks to quickly find connected friend groups and in network connectivity problems.

💼 Career

Understanding Union Find is important for software engineers working on graph algorithms, network design, and optimization problems.

1

Create the initial parent array

Create a variable called n and set it to 5. Then create an array called parent of length n where each element is its own index (0 to 4).

DSA Javascript

# Your code here

Hint

Use a for loop from 0 to n - 1 to fill the parent array with its own indices.

2

Write the find function with path compression

Write a function called find that takes a parameter x. It should return the leader of x by recursively finding the parent until parent[x] === x. Use path compression by setting parent[x] to the result of the recursive call.

DSA Javascript

const n = 5;
const parent = [];
for (let i = 0; i < n; i++) {
    parent[i] = i;
}

// Write the find function with path compression
// Your code here

Hint

Use recursion and update parent[x] to the leader found to compress the path.

3

Write the union function to merge groups

Write a function called union that takes two parameters a and b. It should find the leaders of a and b using the find function. If the leaders are different, set the parent of b's leader to a's leader to merge the groups.

DSA Javascript

const n = 5;
const parent = [];
for (let i = 0; i < n; i++) {
    parent[i] = i;
}

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

// Write the union function to merge two groups
// Your code here

Hint

Find leaders of both elements and link one leader to the other if they differ.

4

Perform unions and print the parent array

Call union(0, 1), union(1, 2), and union(3, 4). Then print the parent array using console.log(parent) to show the effect of path compression.

DSA Javascript

const n = 5;
const parent = [];
for (let i = 0; i < n; i++) {
    parent[i] = i;
}

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

function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA !== rootB) {
        parent[rootB] = rootA;
    }
}

// Perform unions and print the parent array
// Your code here

Hint

After unions, the parent array should show leaders for each group. Printing parent shows the compressed paths.

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