Path Compression in Union Find in DSA C

Mental Model

Path compression flattens the structure of the union find tree by making nodes point directly to the root, speeding up future searches.

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 can find the root ancestor faster next time.

Before path compression:
1 -> 2 -> 3 -> 4 -> null
After path compression:
1 -> 4
2 -> 4
3 -> 4
4 -> null

Dry Run Walkthrough

Input: Union find with elements 1 to 4, where 1 is connected to 2, 2 to 3, and 3 to 4. Find root of 1 with path compression.

Goal: Find the root of element 1 and update all nodes on the path to point directly to the root to speed up future finds.

Step 1: Start find operation on element 1, see parent is 2

1 -> [curr->2] -> 3 -> 4 -> null

Why: We need to find the root by following parents

Step 2: Move to parent 2, see parent is 3

1 -> 2 -> [curr->3] -> 4 -> null

Why: Continue moving up to find root

Step 3: Move to parent 3, see parent is 4

1 -> 2 -> 3 -> [curr->4] -> null

Why: Keep moving up until root found

Step 4: Parent of 4 is itself, root found. Start path compression back to 1

1 -> 2 -> 3 -> 4 -> null

Why: Root is 4, now update parents on path

Step 5: Update parent of 3 to 4

1 -> 2 -> 3 -> 4 -> null (3 points directly to 4)

Why: Flatten tree for faster future finds

Step 6: Update parent of 2 to 4

1 -> 2 -> 3 -> 4 -> null (2 points directly to 4)

Why: Continue flattening

Step 7: Update parent of 1 to 4

1 -> 4
2 -> 4
3 -> 4
4 -> null

Why: All nodes on path now point directly to root

Result:

1 -> 4
2 -> 4
3 -> 4
4 -> null
Root of 1 is 4

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

int parent[SIZE];

// Initialize each element to be its own parent
void make_set() {
    for (int i = 1; i < SIZE; i++) {
        parent[i] = i;
    }
}

// Find with path compression
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // path compression step
    }
    return parent[x];
}

// Union two sets
void union_sets(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}

// Print parents array
void print_parents() {
    for (int i = 1; i < SIZE; i++) {
        printf("%d -> %d\n", i, parent[i]);
    }
}

int main() {
    make_set();
    union_sets(1, 2); // 1->2
    union_sets(2, 3); // 2->3
    union_sets(3, 4); // 3->4

    printf("Parents before find with path compression:\n");
    print_parents();

    int root = find(1); // triggers path compression

    printf("\nParents after find(1) with path compression:\n");
    print_parents();

    printf("\nRoot of 1 is %d\n", root);

    return 0;
}

if (parent[x] != x) {

Check if current node is not root

parent[x] = find(parent[x]); // path compression step

Recursively find root and update parent to root to flatten tree

return parent[x];

Return root of current node

Output

Parents before find with path compression:

1 -> 2

2 -> 3

3 -> 4

4 -> 4



Parents after find(1) with path compression:

1 -> 4

2 -> 4

3 -> 4

4 -> 4



Root of 1 is 4

Complexity Analysis

Time: O(α(n)) where α is the inverse Ackermann function, almost constant, because path compression flattens the tree making future finds very fast

Space: O(n) for the parent array storing each element's parent

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

Edge Cases

Find on element that is root itself

Returns element immediately without recursion

DSA C

if (parent[x] != x) {

Find on element with single parent

Updates parent to root directly after recursion

DSA C

parent[x] = find(parent[x]); // path compression step

Union of two elements already in same set

No change to parents, avoids cycle

DSA C

if (rootA != rootB) {

When to Use This Pattern

When you see problems asking for efficient union and find operations on sets, especially with repeated queries, reach for union find with path compression to speed up find operations.

Common Mistakes

Mistake: Not updating the parent during find, missing path compression
Fix: Assign parent[x] = find(parent[x]) to flatten the tree

Mistake: Union without using find to get roots, causing incorrect parent assignments
Fix: Always find roots before union to avoid cycles

Summary

It finds the root of an element and flattens the tree by making nodes point directly to the root.

Use it when you need fast repeated union and find operations on disjoint sets.

The key insight is updating parents during find to speed up all future searches.

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)