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.