Path Compression in Union Find in DSA Rust - Execution Trace

Concept Flow - Path Compression in Union Find

Start: Find(x)

↓

Is parent[x

↓

Return x

↓

Set parent[x

↓

Return root

Path compression flattens the tree by making each node point directly to the root during find operation.

Execution Sample

DSA Rust

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

This function finds the root of x and compresses the path by pointing x directly to the root.

Execution Table

Step	Operation	Node x	parent[x] before	Recursive call	parent[x] after	Visual State
1	Call find(3)	3	1	find(1)	1	parent = [0, 2, 2, 1, 4]
2	Call find(1)	1	2	find(2)	2	parent = [0, 2, 2, 1, 4]
3	Call find(2)	2	2	No recursion (root)	2	parent = [0, 2, 2, 1, 4]
4	Return from find(2)	1	2	Set parent[1] = 2	2	parent = [0, 2, 2, 1, 4]
5	Return from find(1)	3	1	Set parent[3] = 2	2	parent = [0, 2, 2, 2, 4]
6	Final return	3	2	Return 2	2	parent = [0, 2, 2, 2, 4]

💡 Recursion ends when parent[x] == x (node 2 is root). Path compression updates parent pointers on return.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
parent[3]	1	1	1	1	1	2	2
parent[1]	2	2	2	2	2	2	2
parent[2]	2	2	2	2	2	2	2
parent vector	[0,2,2,1,4]	[0,2,2,1,4]	[0,2,2,1,4]	[0,2,2,1,4]	[0,2,2,1,4]	[0,2,2,2,4]	[0,2,2,2,4]

Key Moments - 3 Insights

Why does find(3) call find(1) and then find(2)?

Because parent[3] = 1, so to find root of 3, we must find root of 1. Then parent[1] = 2, so find(2) is called. This is shown in execution_table steps 1-3.

How does path compression update parent pointers?

On returning from recursion, parent[x] is set to root. For example, parent[1] and parent[3] are updated to 2 in steps 4 and 5, flattening the tree.

Why does recursion stop at node 2?

Because parent[2] == 2, meaning node 2 is the root. This is the base case stopping recursion as shown in step 3.

Visual Quiz - 3 Questions

Look at the execution_table, what is parent[3] after step 5?

A 3

B 1

C 2

D 0

💡 Hint

Check the 'parent[x] after' column at step 5 for node 3.

At which step does the recursion stop because parent[x] == x?

A Step 3

B Step 5

C Step 1

D Step 6

💡 Hint

Look for the step where 'Recursive call' is 'No recursion (root)'.

If parent[1] was initially 1 instead of 2, how would the path compression change?

A parent[3] would point directly to 2

B parent[3] would point directly to 1

C No change in parent pointers

D parent[1] would point to 3

💡 Hint

Check how parent pointers update after recursion returns in the execution_table.

Concept Snapshot

Path Compression in Union Find:
- Used in find operation to flatten tree.
- Recursively find root of x.
- Set parent[x] directly to root on return.
- Speeds up future find calls.
- Keeps tree shallow for efficiency.

Full Transcript

Path Compression in Union Find is a technique to speed up the find operation by making nodes point directly to the root. The find function recursively finds the root of a node. If the node is not its own parent, it calls find on its parent. After finding the root, it sets the node's parent to the root, flattening the tree. This reduces the height of the tree and speeds up future operations. The recursion stops when a node is its own parent, which is the root. The execution table shows step-by-step how parent pointers update during the find operation with path compression.

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