Path Compression in Union Find in DSA Java

Mental Model

Path compression makes finding the group leader faster by flattening the structure during searches.

Analogy: Imagine a family tree where each person points to their parent. Path compression is like updating everyone on the path to point directly to the oldest ancestor, so future lookups are quicker.

1 -> 2 -> 3 -> 4 -> null
↑root points to 1
Initially, each node points to its parent forming a chain.

Dry Run Walkthrough

Input: Union sets: union(1,2), union(2,3), union(3,4); then find(4)

Goal: Find the leader of element 4 and compress the path so future finds are faster

Step 1: union(1,2) merges sets containing 1 and 2

parent[1]=1, parent[2]=1, parent[3]=3, parent[4]=4

Why: We link 2's parent to 1 to form a set {1,2}

Step 2: union(2,3) merges sets containing 2 and 3

parent[1]=1, parent[2]=1, parent[3]=1, parent[4]=4

Why: 3's parent points to 1 through 2, so 3 joins the set {1,2,3}

Step 3: union(3,4) merges sets containing 3 and 4

parent[1]=1, parent[2]=1, parent[3]=1, parent[4]=1

Why: 4's parent points to 1 through 3, so 4 joins the set {1,2,3,4}

Step 4: find(4) starts, path is 4 -> 1

parent[4]=1 (before compression)

Why: We need to find the root of 4 which is 1

Step 5: path compression updates parent of 4 directly to 1

parent[4]=1 (after compression)

Why: Directly linking 4 to root 1 speeds up future finds

Result:

parent array: [1,1,1,1] meaning all nodes point directly to root 1

Annotated Code

DSA Java

public class UnionFind {
    private int[] parent;

    public UnionFind(int size) {
        parent = new int[size + 1];
        for (int i = 1; i <= size; i++) {
            parent[i] = i; // each node is its own parent initially
        }
    }

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

    public void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA; // merge sets by linking rootB to rootA
        }
    }

    public void printParents(int size) {
        for (int i = 1; i <= size; i++) {
            System.out.print(parent[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(4);
        uf.union(1, 2);
        uf.union(2, 3);
        uf.union(3, 4);
        System.out.println("Root of 4: " + uf.find(4));
        uf.printParents(4);
    }
}

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

compress path by linking current node directly to root

int rootA = find(a); int rootB = find(b);

find leaders of both sets to decide union

if (rootA != rootB) { parent[rootB] = rootA; }

merge sets by linking root of one to the other

Output

Root of 4: 1

1 1 1 1 

Complexity Analysis

Time: O(α(n)) per find/union operation because path compression flattens the tree making future operations almost constant time

Space: O(n) for storing the parent array for n elements

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

Edge Cases

find on element that is its own parent (single element set)

returns the element itself immediately

DSA Java

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

union of two elements already in the same set

no change to parent array

DSA Java

if (rootA != rootB) { parent[rootB] = rootA; }

union or find on invalid element (out of range)

not handled explicitly, may cause error

DSA Java

No explicit guard in code

When to Use This Pattern

When you need to quickly check if two elements belong to the same group and merge groups efficiently, use Union Find with path compression to speed up repeated queries.

Common Mistakes

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

Mistake: Linking parent of rootA to rootB instead of rootB to rootA in union
Fix: Ensure union links rootB to rootA or vice versa consistently to avoid cycles

Summary

It speeds up finding the leader of a set by flattening the tree structure during find operations.

Use it when you have many union and find operations on disjoint sets to keep queries fast.

The key is to update each node on the path to point directly to the root, making future finds almost instant.

Practice

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

easy

A. To merge two sets by size

B. To speed up the find operation by flattening the tree structure

C. To initialize the parent array

D. To count the number of connected components

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 structure -> Option B

4. Quick Check:

   Path compression = flatten tree for faster find [OK]

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

Common Mistakes:

• Confusing path compression with union by size/rank
• Thinking it merges sets instead of optimizing find
• Assuming it initializes data structures

2. Which of the following is the correct Java method signature for the find function implementing path compression in Union Find?

easy

A. public int find(int x)

B. public void find(int x)

C. public boolean find(int x)

D. public int find()"

Solution

1. Step 1: Understand the return type of find

   The find method returns the representative (root) of the set containing element x, so it returns an integer.

2. Step 2: Check method parameters

   The method must accept the element x as input to find its root.

3. Final Answer:

   public int find(int x) -> Option A

4. Quick Check:

   find returns root index as int [OK]

Hint: find returns int root and takes int parameter [OK]

Common Mistakes:

• Using void return type for find
• Missing parameter for element to find
• Returning boolean instead of int

3. Consider the following Java code snippet implementing path compression in Union Find:

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

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

System.out.println(find(4));
System.out.println(Arrays.toString(parent));

What is the output?

medium

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

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

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

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

Solution

1. Step 1: Trace find(4) call with path compression

   parent[4]=3 -> find(3); parent[3]=2 -> find(2); parent[2]=1 -> find(1); parent[1]=0 -> find(0)=0 (base); parent[1]=0; parent[2]=0; parent[3]=0; parent[4]=0. Returns 0.

2. Step 2: Update parent array after path compression

   Entire path flattens: parent = [0, 0, 0, 0, 0].

3. Final Answer:

   0 [0, 0, 0, 0, 0] -> Option C

4. Quick Check:

   find(4) = 0, all path nodes point to root 0 [OK]

Hint: Path compression flattens entire path to root [OK]

Common Mistakes:

• Thinking only leaf updates (partial compression)
• Expecting no change in parent array
• Misreading recursion depth or base case

4. The following find method is intended to implement path compression but has a bug:

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

What is the bug and how to fix it?

medium

A. Missing path compression assignment; fix by adding parent[x] = find(parent[x]);

B. Incorrect base case; fix by changing parent[x] == x to parent[x] != x

C. Wrong return type; fix by changing return type to void

D. No bug; code is correct

Solution

1. Step 1: Identify missing path compression step

   The method recursively finds the root but does not update parent[x] to root, so no path compression happens.

2. Step 2: Fix by assigning compressed parent

   Adding parent[x] = find(parent[x]); before returning compresses the path.

3. Final Answer:

   Missing path compression assignment; fix by adding parent[x] = find(parent[x]); -> Option A

4. Quick Check:

   Assign parent[x] = find(parent[x]) for compression [OK]

Hint: Always assign parent[x] = find(parent[x]) to compress path [OK]

Common Mistakes:

• Forgetting to update parent[x]
• Changing base case incorrectly
• Returning void instead of int

5. Given a Union Find structure with parent = {0, 0, 1, 2, 4, 5} and rank = {0, 1, 2, 3, 4, 5}, after performing union(4, 5) and then find(5) with path compression, what will be the updated parent array?

hard

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

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

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

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

Solution

1. Step 1: Perform union(4, 5) by rank

   Ranks: rank[4]=4, rank[5]=5. Since rank[5] > rank[4], parent[4] = 5. But ranks given are increasing, so actually rank[5] is highest, so parent[4] = 5.

2. Step 2: Perform find(5) with path compression

   find(5) returns 5 (root). Path compression updates parent of 5 to itself (no change). But parent[4] points to 5, so parent array is [0,0,1,2,5,5].

3. Step 3: Check options

   [0, 0, 1, 2, 4, 4] shows parent[5] = 4, which contradicts union by rank. [0, 0, 1, 2, 3, 4] no change. [0, 0, 1, 2, 3, 3] parent[5]=3 incorrect. [0, 0, 1, 2, 5, 5] parent[4]=5 and parent[5]=5 matches expected.

4. Final Answer:

   [0, 0, 1, 2, 5, 5] -> Option D

5. Quick Check:

   Union by rank sets parent of lower rank to higher [OK]

Hint: Union by rank attaches lower rank root to higher rank root [OK]

Common Mistakes:

• Confusing which parent to update in union
• Ignoring rank comparison
• Assuming parent array unchanged after union