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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Find with Path Compression

What is the output of the following C# code that uses path compression in a Union Find structure?

DSA C#

using System;

class UnionFind {
    private int[] parent;

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

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

    public void Union(int a, int b) {
        int rootA = Find(a);
        int rootB = Find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA;
        }
    }

    public void PrintParents() {
        for (int i = 0; i < parent.Length; i++) {
            Console.Write(parent[i] + " ");
        }
        Console.WriteLine();
    }
}

class Program {
    static void Main() {
        UnionFind uf = new UnionFind(5);
        uf.Union(0, 1);
        uf.Union(1, 2);
        uf.Union(3, 4);
        uf.Find(2);
        uf.PrintParents();
    }
}

A 0 0 0 3 3

B 0 0 1 3 4

C 0 1 2 3 4

D 0 0 0 4 4

💡 Hint

Remember that Find compresses the path by making nodes point directly to the root.

After unions, 0,1,2 are connected with 0 as root, and 3,4 connected with 3 as root. Calling Find(2) compresses the path so 2 points directly to 0. The parents array shows roots for each element.

❓ Predict Output

intermediate

Result of Multiple Finds with Path Compression

What will be printed after running this C# code with path compression in Union Find?

DSA C#

using System;

class UnionFind {
    private int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

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

    public void Union(int a, int b) {
        int rootA = Find(a);
        int rootB = Find(b);
        if (rootA != rootB) parent[rootB] = rootA;
    }

    public void PrintParents() {
        foreach (var p in parent) Console.Write(p + " ");
        Console.WriteLine();
    }
}

class Program {
    static void Main() {
        UnionFind uf = new UnionFind(6);
        uf.Union(0, 1);
        uf.Union(1, 2);
        uf.Union(2, 3);
        uf.Union(4, 5);
        uf.Find(3);
        uf.Find(5);
        uf.PrintParents();
    }
}

A 0 0 0 0 4 4

B 0 1 2 3 4 5

C 0 0 0 0 0 0

D 0 0 1 0 4 4

💡 Hint

Path compression updates parents to root after Find calls.

After unions, 0-3 are connected with 0 as root, 4-5 connected with 4 as root. Finds compress paths so 1,2,3 point directly to 0 and 5 points to 4.

🔧 Debug

advanced

Identify the Error in Path Compression Implementation

What error will this C# code produce when running the Find method with path compression?

DSA C#

class UnionFind {
    private int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

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

A StackOverflowException due to infinite recursion

B SyntaxError: Missing return statement in all code paths

C NullReferenceException because parent array is null

D No error, code runs correctly

💡 Hint

Check if all paths in Find method return a value.

The else branch does not return a value after assigning parent[x]. This causes a compile-time error for missing return statement.

❓ Predict Output

advanced

Final Parents Array After Complex Unions and Finds

What is the final state of the parents array after executing this C# Union Find code with path compression?

DSA C#

using System;

class UnionFind {
    private int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

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

    public void Union(int a, int b) {
        int rootA = Find(a);
        int rootB = Find(b);
        if (rootA != rootB) parent[rootB] = rootA;
    }

    public void PrintParents() {
        foreach (var p in parent) Console.Write(p + " ");
        Console.WriteLine();
    }
}

class Program {
    static void Main() {
        UnionFind uf = new UnionFind(7);
        uf.Union(0, 1);
        uf.Union(1, 2);
        uf.Union(3, 4);
        uf.Union(5, 6);
        uf.Union(4, 5);
        uf.Find(6);
        uf.Find(2);
        uf.PrintParents();
    }
}

A 0 1 2 3 4 5 6

B 0 0 0 3 3 4 4

C 0 0 0 0 0 0 0

D 0 0 0 3 3 3 3

💡 Hint

Consider how unions connect sets and how finds compress paths.

Unions connect 0-1-2 with root 0, 3-4-5-6 with root 3 after union of 4 and 5. Finds compress paths so 6 points to 3 and 2 points to 0.

🧠 Conceptual

expert

Effect of Path Compression on Union Find Tree Height

Which statement best describes the effect of path compression on the height of trees in a Union Find data structure?

A Path compression does not affect tree height but only speeds up union operations.

B Path compression increases tree height by adding extra parent links to nodes.

C Path compression flattens trees by making nodes point directly to the root, reducing tree height drastically over time.

D Path compression removes nodes from the tree to reduce height.

💡 Hint

Think about how path compression changes parent pointers during Find.

Path compression shortens paths by making every node on the find path point directly to the root, effectively flattening the tree and reducing height.

Practice

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

easy

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

B. To merge two sets without checking their roots

C. To delete elements from the set efficiently

D. To sort the elements in each set

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 -> Option A

4. Quick Check:

   Path compression = flatten tree = faster find [OK]

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

Common Mistakes:

• Thinking path compression merges sets
• Confusing path compression with union by rank
• Believing it deletes elements

2. Which of the following is the correct syntax for the find method 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) { return parent[x]; }

C. int Find(int x) { if (parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; }

D. int Find(int x) { if (parent[x] == x) return x; else return Find(x); }

Solution

1. Step 1: Check for path compression in the code

   int Find(int 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: Verify other options

   int Find(int x) { while (parent[x] != x) x = parent[x]; return x; } uses a loop but does not update parents. int Find(int x) { return parent[x]; } returns parent directly without recursion. int Find(int x) { if (parent[x] == x) return x; else return Find(x); } causes infinite recursion.

3. Final Answer:

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

4. Quick Check:

   Path compression updates parent during find [OK]

Hint: Look for recursive parent update in find method [OK]

Common Mistakes:

• Using loop without updating parents
• Returning parent without recursion
• Infinite recursion by calling Find(x) instead of Find(parent[x])

3. Given the following code snippet, what will be the output after calling uf.Find(3)?

var uf = new UnionFind(5);
uf.Union(1, 2);
uf.Union(2, 3);
Console.WriteLine(uf.Find(3));

Assume Union merges sets by attaching root of second to first and Find uses path compression.

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace the unions

   Union(1,2) makes 1 the root of 2. Union(2,3) attaches 3 under 2, so root of 3 is 1 through 2.

2. Step 2: Find root of 3 with path compression

   Find(3) follows parent chain 3 -> 2 -> 1, returns 1 and compresses path so 3 points directly to 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Root after unions = 1 [OK]

Hint: Follow parent chain after unions to find root [OK]

Common Mistakes:

• Assuming root is 3 or 2 without tracing
• Ignoring path compression effect
• Confusing union direction

4. Identify the bug in this Find method implementation with path compression:

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

medium

A. It should use a loop instead of recursion

B. It does not return the root correctly

C. It does not perform path compression

D. It causes infinite recursion because it calls Find(x) instead of Find(parent[x])

Solution

1. Step 1: Analyze the recursive call

   The method calls Find(x) again without changing x, causing infinite recursion.

2. Step 2: Correct recursive call for path compression

   It should call Find(parent[x]) to move up the tree and compress paths.

3. Final Answer:

   It causes infinite recursion because it calls Find(x) instead of Find(parent[x]) -> Option D

4. Quick Check:

   Recursive call must use parent[x] [OK]

Hint: Recursive find must call Find(parent[x]) not Find(x) [OK]

Common Mistakes:

• Calling Find(x) again causes infinite loop
• Forgetting to update parent for compression
• Using loop but missing path compression

5. You have a Union Find with 6 elements (0 to 5). After these operations:

uf.Union(0, 1);
uf.Union(1, 2);
uf.Union(3, 4);
uf.Union(4, 5);
uf.Find(2);
uf.Find(5);
uf.Union(2, 5);
uf.Find(5);

How many elements will directly point to the root of their set after all operations with path compression?

hard

A. 6

B. 4

C. 3

D. 2

Solution

1. Step 1: Track unions and finds

   Unions create two sets: {0,1,2} and {3,4,5}. Finds on 2 and 5 compress paths so 0 and 3 become roots with direct children.

2. Step 2: After union(2,5) and find(5), all nodes in one set with path compression

   After union(2,5), sets merge. Find(5) compresses path so nodes 2 and 5 point directly to root. Nodes 0 and 1 also point to root from earlier compression.

3. Step 3: Count elements directly pointing to root

   Elements 0,1,2,3,4,5 all point directly to the root after the final find(5) call due to path compression.

4. Final Answer:

   6 -> Option A

5. Quick Check:

   All nodes point directly to root after final find call [OK]

Hint: Count nodes updated by find calls for direct root pointers [OK]

Common Mistakes:

• Assuming all nodes point directly after union
• Ignoring path compression effect only on find calls
• Counting nodes without tracing parent updates