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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of find operation with path compression

What is the output of the following code snippet that performs find operations with path compression on a Union Find structure?

DSA C

int parent[6] = {0, 0, 1, 2, 3, 4};

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

int main() {
    printf("%d\n", find(5));
    printf("%d\n", parent[5]);
    return 0;
}

A

5
5

B

4
4

C

0
0

D

1
0

💡 Hint

Trace the parent array and see how path compression updates parent[5].

The initial parent array is [0, 0, 1, 2, 3, 4]. The find(5) call recursively finds the root parent of 5:

• parent[5] = 4, so find(4) is called.
• parent[4] = 3, so find(3) is called.
• parent[3] = 2, so find(2) is called.
• parent[2] = 1, so find(1) is called.
• parent[1] = 0, so find(0) is called.
• parent[0] = 0, so root is 0.

Path compression sets parent of all nodes in the path directly to 0. So parent[5] becomes 0.

Output is 0 (root) and parent[5] after compression is 0.

🧠 Conceptual

intermediate

Effect of path compression on parent array

Given a Union Find parent array: [0, 0, 1, 2, 3, 4], after calling find(5) with path compression, what will be the updated parent array?

A [0, 0, 1, 2, 3, 0]

B [0, 0, 0, 0, 0, 0]

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

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

💡 Hint

Path compression updates parents along the path to the root.

Calling find(5) triggers recursive path compression, setting the parent of every node on the path 5→4→3→2→1→0 directly to the root 0. Thus, parent[1..5] all become 0 (parent[1] already was). Updated array: [0, 0, 0, 0, 0, 0].

🔧 Debug

advanced

Identify the bug in path compression implementation

What error will the following code cause when calling find(3)?

DSA C

int parent[4] = {0, 0, 1, 2};

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

int main() {
    printf("%d\n", find(3));
    return 0;
}

A Correct output: 0

B Runtime error: segmentation fault

C Compilation error: missing return statement

D Stack overflow due to infinite recursion

💡 Hint

Check if path compression is applied and if parent array changes.

The find function correctly computes the root (0) for node 3 via recursion: 3→2→1→0, stopping since parent[0] == 0. However, it lacks path compression as there is no parent[x] = find(parent[x]) update. No errors occur: compiles fine, runs without segfault or stack overflow, outputs 0.

The implementation bug is missing path compression, but the question asks for errors caused by calling find(3), of which there are none.

❓ Predict Output

advanced

Output after union and find with path compression

What is the output of the following code snippet?

DSA C

int parent[5] = {0, 1, 2, 3, 4};

void union_set(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
    }
}

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

int main() {
    union_set(0, 1);
    union_set(1, 2);
    union_set(3, 4);
    printf("%d\n", find(2));
    printf("%d\n", parent[2]);
    printf("%d\n", find(4));
    return 0;
}

A

0
0
3

B

1
1
3

C

0
1
4

D

2
0
4

💡 Hint

Trace unions and path compression updates carefully.

Unions:

• union_set(0,1): parent[1] = 0
• union_set(1,2): find(1) = 0, find(2) = 2, parent[2] = 0
• union_set(3,4): parent[4] = 3

Find(2): parent[2] = 0, so root is 0. Path compression sets parent[2] = 0.

parent[2] after find is 0.

Find(4): parent[4] = 3, root is 3.

🧠 Conceptual

expert

Time complexity impact of path compression

Which statement best describes the time complexity impact of path compression in Union Find operations?

A Path compression makes union operations slower but find operations faster.

B Path compression increases the worst-case time complexity to linear per find operation.

C Path compression has no effect on time complexity but reduces memory usage.

D Path compression reduces the amortized time per find operation to nearly constant, specifically inverse Ackermann function time.

💡 Hint

Consider how path compression flattens the tree structure over multiple operations.

Path compression flattens the tree, making future find operations faster. The amortized time per find becomes almost constant, bounded by the inverse Ackermann function, which grows extremely slowly.

Practice

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

easy

A. To initialize the parent array

B. To merge two sets by size

C. To count the number of connected components

D. To speed up the find operation by making nodes point directly to the root

Solution

1. Step 1: Understand the find operation

   The find operation locates the root parent of a node in Union Find.

2. Step 2: Role of path compression

   Path compression makes all nodes on the path point directly to the root, speeding up future find calls.

3. Final Answer:

   To speed up the find operation by making nodes point directly to the root -> Option D

4. Quick Check:

   Path compression optimizes find = C [OK]

Hint: Path compression flattens tree for faster find [OK]

Common Mistakes:

• Confusing path compression with union by size
• Thinking it initializes the structure
• Believing it counts components

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

easy

A. int find(int x) { while(parent[x] != x) x = parent[x]; return x; }

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

C. int find(int x) { if(parent[x] == x) return x; else return find(parent[x]); }

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

Solution

1. Step 1: Identify path compression in code

   Path compression updates parent[x] during recursion to root.

2. Step 2: Check each option

   int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } updates parent[x] with recursive find result, implementing path compression correctly.

3. Final Answer:

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

4. Quick Check:

   Path compression updates parent recursively = A [OK]

Hint: Look for parent update inside find recursion [OK]

Common Mistakes:

• Using loop without updating parent (Option B)
• Not updating parent during recursion (Option C)
• Resetting parent incorrectly (Option D)

3. Given the following Union Find structure with parent = [0, 0, 1, 2, 3], what will be the parent array after calling find(4) with path compression?

medium

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

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

C. [0, 1, 1, 2, 3]

D. [0, 0, 1, 3, 3]

Solution

1. Step 1: Trace find(4) path

   4's parent is 3, 3's parent is 2, 2's parent is 1, 1's parent is 0, which is root.

2. Step 2: Apply path compression

   All nodes on path (4,3,2,1) update parent to root 0 (parent[1] already 0). parent[2]=0, parent[3]=0, parent[4]=0. So parent array becomes [0,0,0,0,0].

3. Final Answer:

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

4. Quick Check:

   Path compression sets parent[4] = 0 = A [OK]

Hint: Update all parents on path to root after find [OK]

Common Mistakes:

• Only updating parent[4] to root (Option B)
• Not updating any parent (Option C)
• Updating wrong parents (Option D)

4. Identify the bug in this find function with path compression:

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

medium

A. No bug, code is correct

B. Incorrect base case condition

C. Missing return value from recursive call before assignment

D. Parent update should be after return

Solution

1. Step 1: Analyze recursive call

   The recursive call find(parent[x]) is made but its return value is ignored.

2. Step 2: Check parent update

   Parent update uses parent[parent[x]] instead of the root returned by recursion, so path compression fails.

3. Final Answer:

   Missing return value from recursive call before assignment -> Option C

4. Quick Check:

   Return value must be assigned to parent[x] = D [OK]

Hint: Assign recursive find result to parent[x] for compression [OK]

Common Mistakes:

• Ignoring recursive return value
• Updating parent incorrectly
• Misunderstanding base case

5. You have a Union Find with 5 elements and parent = [0, 0, 1, 2, 3]. After calling union(4, 0) and then find(4) with path compression, what is the final parent array?

hard

A. [0, 0, 1, 2, 0]

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

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

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

Solution

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

   Find roots: root(4) = 4 (chain 4->3->2->1->0), root(0) = 0. Since roots differ, link root(4) to root(0). So parent[4] = 0. Updated parent = [0, 0, 1, 2, 0].

2. Step 2: Call find(4) with path compression

   Path: 4 -> 0. Since 0 is root, parent[4] already 0, no further updates. Final parent = [0, 0, 1, 2, 0].

3. Final Answer:

   [0, 0, 1, 2, 0] -> Option A

4. Quick Check:

   Union links 4 to 0, find compresses path = A [OK]

Hint: Union links roots, find compresses path to root [OK]

Common Mistakes:

• Incorrectly linking assuming same root (Option C)
• Wrong union target (Option B)
• Incomplete path compression (Option D)