Path Compression in Union Find in DSA C#

Mental Model

Path compression makes finding the group leader faster by making nodes point directly to the leader.

Analogy: Imagine a family tree where each person points to their parent. Path compression is like updating everyone in a branch to point directly to the oldest ancestor, so you find the leader faster next time.

0 -> 1 -> 2 -> 3 -> null
↑
start

Dry Run Walkthrough

Input: Union-Find with elements 0 to 3, unions: union(0,1), union(1,2), find(2)

Goal: Show how path compression updates the parent links during find to speed up future finds

Step 1: union(0,1): make 0 the parent of 1

parent: [0, 0, 2, 3]

Why: We connect 1 under 0 to form a group

Step 2: union(1,2): find leaders of 1 and 2, then connect 2 under 0

parent: [0, 0, 0, 3]

Why: Since 1's leader is 0, we connect 2 under 0 to keep one group

Step 3: find(2): path compression updates 2's parent directly to 0

parent: [0, 0, 0, 3]

Why: 2 already points to 0, so no change but confirms direct link

Step 4: find(1): path compression updates 1's parent directly to 0

parent: [0, 0, 0, 3]

Why: 1 already points to 0, confirming direct link

Result:

parent array after path compression: [0, 0, 0, 3]

Annotated Code

DSA C#

using System;

class UnionFind
{
    private int[] parent;
    private int[] rank;

    public UnionFind(int size)
    {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++)
        {
            parent[i] = i; // each node is its own parent initially
            rank[i] = 0; // rank used to keep tree shallow
        }
    }

    public int Find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = Find(parent[x]); // path compression: update parent to leader
        }
        return parent[x];
    }

    public void Union(int x, int y)
    {
        int rootX = Find(x); // find leader of x
        int rootY = Find(y); // find leader of y

        if (rootX == rootY) return; // already in same group

        // union by rank to keep tree shallow
        if (rank[rootX] < rank[rootY])
        {
            parent[rootX] = rootY;
        }
        else if (rank[rootX] > rank[rootY])
        {
            parent[rootY] = rootX;
        }
        else
        {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

    public void PrintParents()
    {
        Console.WriteLine(string.Join(", ", parent));
    }
}

class Program
{
    static void Main()
    {
        UnionFind uf = new UnionFind(4);
        uf.Union(0, 1);
        uf.Union(1, 2);
        uf.Find(2); // triggers path compression
        uf.Find(1); // triggers path compression
        uf.PrintParents(); // print final parent array
    }
}

if (parent[x] != x) { parent[x] = Find(parent[x]); // path compression: update parent to leader }

compress path by making current node point directly to leader

int rootX = Find(x); // find leader of x int rootY = Find(y); // find leader of y

find leaders of both nodes before union

if (rootX == rootY) return; // already in same group

skip union if both nodes share leader

if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; }

attach smaller tree under bigger tree to keep shallow

Output

0, 0, 0, 3

Complexity Analysis

Time: O(α(n)) per operation, where α is inverse Ackermann function, almost constant because path compression flattens trees

Space: O(n) for parent and rank arrays storing each element's info

vs Alternative: Without path compression, find can be O(n) in worst case; path compression reduces it to almost O(1) amortized

Edge Cases

Find on element that is its own parent

Returns element itself immediately without recursion

DSA C#

if (parent[x] != x)

Union of two elements already in same set

No changes made, avoids unnecessary work

DSA C#

if (rootX == rootY) return;

Union with rank tie

One root becomes parent and its rank increases by one

DSA C#

else
        {
            parent[rootY] = rootX;
            rank[rootX]++;

When to Use This Pattern

When you need to quickly find and merge groups repeatedly, use Union Find with path compression to speed up repeated find operations by flattening the structure.

Common Mistakes

Mistake: Not updating the parent during find, missing path compression
Fix: Assign parent[x] = Find(parent[x]) inside the Find method to compress paths

Mistake: Not checking if two elements are already connected before union
Fix: Add a check if rootX == rootY to skip union if already connected

Summary

It speeds up finding the leader of a group by making nodes point directly to the leader.

Use it when you have many union and find operations on groups of elements.

The key is updating parents during find to flatten the tree and make future finds faster.

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