Path Compression in Union Find in DSA Rust

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

0 -> 1 -> 2 -> 3 -> null
↑
current node

Dry Run Walkthrough

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

Goal: Find the leader of element 2 and compress the path so 2 points directly to the leader

Step 1: union(0,1): make 1 point to 0

0 -> 0
1 -> 0
2 -> 2
3 -> 3

Why: We connect 1 to 0 to show they are in the same group

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

0 -> 0
1 -> 0
2 -> 0
3 -> 3

Why: We connect 2 to 0 through 1, so 0 is leader of 0,1,2

Step 3: find(2): follow parent from 2 to 0

2 -> 0 (already direct)
1 -> 0
0 -> 0
3 -> 3

Why: 2 already points to leader 0, so no change

Result:

0 -> 0
1 -> 0
2 -> 0
3 -> 3
Leader of 2 is 0

Annotated Code

DSA Rust

struct UnionFind {
    parent: Vec<usize>,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        Self { parent: (0..size).collect() }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]); // path compression
        }
        self.parent[x]
    }

    fn union(&mut self, x: usize, y: usize) {
        let root_x = self.find(x);
        let root_y = self.find(y);
        if root_x != root_y {
            self.parent[root_y] = root_x; // connect root_y to root_x
        }
    }

    fn print_parents(&self) {
        for (i, p) in self.parent.iter().enumerate() {
            println!("{} -> {}", i, p);
        }
    }
}

fn main() {
    let mut uf = UnionFind::new(4);
    uf.union(0, 1);
    uf.union(1, 2);
    let leader = uf.find(2);
    uf.print_parents();
    println!("Leader of 2 is {}", leader);
}

if self.parent[x] != x { self.parent[x] = self.find(self.parent[x]); // path compression }

compress path by making x point directly to its leader

let root_x = self.find(x); let root_y = self.find(y);

find leaders of both elements before union

if root_x != root_y { self.parent[root_y] = root_x; // connect root_y to root_x }

connect one leader to the other to merge groups

Output

0 -> 0

1 -> 0

2 -> 0

3 -> 3

Leader of 2 is 0

Complexity Analysis

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

Space: O(n) for storing parent pointers for each element

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

Edge Cases

find on element that is its own leader

returns element itself immediately without recursion

DSA Rust

if self.parent[x] != x {

union of two elements already in the same group

no change to parent pointers

DSA Rust

if root_x != root_y {

union or find on single element set

element points to itself, no changes needed

DSA Rust

if self.parent[x] != x {

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 pointer during find, missing path compression
Fix: Assign parent[x] = find(parent[x]) to flatten the tree

Mistake: Union without finding leaders first, causing incorrect merges
Fix: Always find leaders of both elements before union

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 to flatten the structure during find so future finds are faster.

Practice

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

easy

A. To merge two sets without checking their roots

B. To speed up future find operations by flattening the tree

C. To delete elements from the Union Find structure

D. To create new sets for each element

Solution

1. Step 1: Understand the role of path compression

   Path compression is used during the find operation to make the tree flatter by pointing nodes directly to the root.

2. Step 2: Effect on future operations

   This flattening reduces the time needed for future find calls, making them faster.

3. Final Answer:

   To speed up future find operations by flattening the tree -> Option B

4. Quick Check:

   Path compression = faster find [OK]

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

Common Mistakes:

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

2. Which of the following Rust function signatures correctly represents a find method with path compression in a Union Find struct?

easy

A. fn find(&mut self, x: usize) -> usize

B. fn find(self, x: usize) -> usize

C. fn find(&self, x: usize) -> usize

D. fn find(x: usize) -> usize

Solution

1. Step 1: Identify mutability requirement

   Path compression modifies the parent array, so self must be mutable reference &mut self.

2. Step 2: Check return type and parameters

   The method takes an element index and returns its root as usize.

3. Final Answer:

   fn find(&mut self, x: usize) -> usize -> Option A

4. Quick Check:

   Mutable self needed for path compression [OK]

Hint: Path compression changes state, so use &mut self [OK]

Common Mistakes:

• Using &self which is immutable
• Taking ownership of self
• Missing self parameter

3. Given the following Rust code snippet implementing path compression in Union Find, what will be the output after calling uf.find(3)?

struct UnionFind {
    parent: Vec<usize>,
}

impl UnionFind {
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }
}

fn main() {
    let mut uf = UnionFind { parent: vec![0, 0, 1, 2] };
    let root = uf.find(3);
    println!("{}", root);
}

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace the parent array before find

   Initial parent: [0, 0, 1, 2]. Element 3 points to 2, 2 points to 1, 1 points to 0.

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

   find(3) calls find(2), which calls find(1), which calls find(0). Since 0 is its own parent, root is 0. Path compression sets parent[3] = 0 and parent[2] = 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Root of 3 after compression = 0 [OK]

Hint: Follow parent chain until self-parent, update parents [OK]

Common Mistakes:

• Stopping at immediate parent without recursion
• Not updating parent during compression
• Confusing indices with values

4. Identify the bug in this Rust find method with path compression and select the correct fix:

fn find(&mut self, x: usize) -> usize {
    if self.parent[x] == x {
        self.parent[x] = self.find(self.parent[x]);
    }
    self.parent[x]
}

medium

A. Change == to != in the if condition

B. Remove the recursive call inside if

C. Return self.parent[self.parent[x]] instead

D. Add a loop instead of recursion

Solution

1. Step 1: Analyze the if condition logic

   The condition self.parent[x] == x means x is root, so no recursion needed. The code wrongly recurses when x is root.

2. Step 2: Correct the condition

   It should recurse only if x is not root, so condition must be self.parent[x] != x.

3. Final Answer:

   Change == to != in the if condition -> Option A

4. Quick Check:

   Recurse only if not root [OK]

Hint: Recurse only when parent differs from node [OK]

Common Mistakes:

• Recursing when node is root
• Forgetting base case
• Misusing equality in condition

5. You have a Union Find with 5 elements initialized as parent = [0,1,2,3,4]. After performing unions union(0,1), union(1,2), and union(3,4), what will be the parent array after calling find(2) with path compression if unions always attach the second root to the first root?

hard

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

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

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

D. [0, 0, 0, 4, 4]

Solution

1. Step 1: Perform unions step-by-step

   union(0,1): parent[1] = 0 -> [0,0,2,3,4] union(1,2): find(1)=0, find(2)=2, parent[2] = 0 -> [0,0,0,3,4] union(3,4): parent[4] = 3 -> [0,0,0,3,3]

2. Step 2: Call find(2) with path compression

   find(2) sees parent[2]=0 which is root, no change. Parents remain [0,0,0,3,3].

3. Final Answer:

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

4. Quick Check:

   Unions attach second root to first, path compression confirms roots [OK]

Hint: Track unions and compress paths to root [OK]

Common Mistakes:

• Not updating parents during union
• Confusing which root attaches to which
• Ignoring path compression effect