Path Compression in Union Find in DSA C# - Execution Trace

Concept Flow - Path Compression in Union Find

Start: Find(x)

↓

Is parent[x

No↓

Recursively Find parent[x

↓

Set parent[x

↓

Return root

The find operation checks if a node is its own parent. If not, it recursively finds the root and updates the node's parent to the root, compressing the path.

Execution Sample

DSA C#

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

This code 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	Find(4)	4	3	Find(3)	To be updated	4->3->2->2
2	Find(3)	3	2	Find(2)	To be updated	3->2->2
3	Find(2)	2	2	No recursion	2	2->2
4	Update parent[3]	3	2	None	2	3->2
5	Update parent[4]	4	3	None	2	4->2
6	Return root	4	2	None	2	Final: 4->2
7	Find(5)	5	5	No recursion	5	5->5
8	Return root	5	5	None	5	Final: 5->5
9	Find(1)	1	1	No recursion	1	1->1
10	Return root	1	1	None	1	Final: 1->1
11	Find(4) again	4	2	No recursion	2	4->2
12	Return root	4	2	None	2	Final: 4->2

💡 Recursion stops when parent[x] == x, meaning root is found.

Variable Tracker

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

Key Moments - 3 Insights

Why do we update parent[x] after the recursive call?

Because after finding the root, we set parent[x] directly to the root to shorten the path, as shown in steps 4 and 5 of the execution_table.

What stops the recursion in Find?

Recursion stops when parent[x] equals x, meaning x is the root. This is shown in step 3 where Find(2) returns immediately.

How does path compression improve future finds?

By updating parent[x] to the root, future Find calls reach the root faster, reducing the chain length, as seen when Find(4) is called again in step 11.

Visual Quiz - 3 Questions

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

A 2

B 3

C 4

D 5

💡 Hint

Check the 'parent[x] after' column at step 5 in the execution_table.

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

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for the step where 'Recursive Call' is 'No recursion' in the execution_table.

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

A Find(4) would compress path to 3

B Find(4) would compress path directly to 4

C Find(4) would compress path to 2 as before

D Find(4) would not compress path

💡 Hint

Consider how the root is found by recursion and where parent[x] is updated in the execution_table.

Concept Snapshot

Path Compression in Union Find:
- Find(x) returns root of x.
- If parent[x] != x, recursively find root.
- Update parent[x] to root to shorten path.
- Speeds up future Find calls.
- Key for efficient Union Find operations.

Full Transcript

Path Compression in Union Find is a technique to speed up the Find operation. When we call Find on a node x, if x is not its own parent, we recursively find the root of x's parent. After finding the root, we update x's parent to point directly to the root. This shortens the path for future Find calls, making them faster. The recursion stops when a node is its own parent, meaning it is the root. This process is shown step-by-step in the execution table, where parent pointers are updated after recursive calls. Path compression is essential for efficient Union Find data structures.

Practice

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

easy

A. To speed up the find operation by flattening the tree

B. To merge two sets without checking their roots

C. To delete elements from the set efficiently

D. To sort the elements in each set

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 -> Option A

4. Quick Check:

   Path compression = flatten tree = faster find [OK]

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

Common Mistakes:

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

2. Which of the following is the correct syntax for the find method 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) { return parent[x]; }

C. int Find(int x) { if (parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; }

D. int Find(int x) { if (parent[x] == x) return x; else return Find(x); }

Solution

1. Step 1: Check for path compression in the code

   int Find(int x) { if (parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; } updates parent[x] to the root during recursion, which is path compression.

2. Step 2: Verify other options

   int Find(int x) { while (parent[x] != x) x = parent[x]; return x; } uses a loop but does not update parents. int Find(int x) { return parent[x]; } returns parent directly without recursion. int Find(int x) { if (parent[x] == x) return x; else return Find(x); } causes infinite recursion.

3. Final Answer:

   int Find(int x) { if (parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; } -> Option C

4. Quick Check:

   Path compression updates parent during find [OK]

Hint: Look for recursive parent update in find method [OK]

Common Mistakes:

• Using loop without updating parents
• Returning parent without recursion
• Infinite recursion by calling Find(x) instead of Find(parent[x])

3. Given the following code snippet, what will be the output after calling uf.Find(3)?

var uf = new UnionFind(5);
uf.Union(1, 2);
uf.Union(2, 3);
Console.WriteLine(uf.Find(3));

Assume Union merges sets by attaching root of second to first and Find uses path compression.

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace the unions

   Union(1,2) makes 1 the root of 2. Union(2,3) attaches 3 under 2, so root of 3 is 1 through 2.

2. Step 2: Find root of 3 with path compression

   Find(3) follows parent chain 3 -> 2 -> 1, returns 1 and compresses path so 3 points directly to 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Root after unions = 1 [OK]

Hint: Follow parent chain after unions to find root [OK]

Common Mistakes:

• Assuming root is 3 or 2 without tracing
• Ignoring path compression effect
• Confusing union direction

4. Identify the bug in this Find method implementation with path compression:

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

medium

A. It should use a loop instead of recursion

B. It does not return the root correctly

C. It does not perform path compression

D. It causes infinite recursion because it calls Find(x) instead of Find(parent[x])

Solution

1. Step 1: Analyze the recursive call

   The method calls Find(x) again without changing x, causing infinite recursion.

2. Step 2: Correct recursive call for path compression

   It should call Find(parent[x]) to move up the tree and compress paths.

3. Final Answer:

   It causes infinite recursion because it calls Find(x) instead of Find(parent[x]) -> Option D

4. Quick Check:

   Recursive call must use parent[x] [OK]

Hint: Recursive find must call Find(parent[x]) not Find(x) [OK]

Common Mistakes:

• Calling Find(x) again causes infinite loop
• Forgetting to update parent for compression
• Using loop but missing path compression

5. You have a Union Find with 6 elements (0 to 5). After these operations:

uf.Union(0, 1);
uf.Union(1, 2);
uf.Union(3, 4);
uf.Union(4, 5);
uf.Find(2);
uf.Find(5);
uf.Union(2, 5);
uf.Find(5);

How many elements will directly point to the root of their set after all operations with path compression?

hard

A. 6

B. 4

C. 3

D. 2

Solution

1. Step 1: Track unions and finds

   Unions create two sets: {0,1,2} and {3,4,5}. Finds on 2 and 5 compress paths so 0 and 3 become roots with direct children.

2. Step 2: After union(2,5) and find(5), all nodes in one set with path compression

   After union(2,5), sets merge. Find(5) compresses path so nodes 2 and 5 point directly to root. Nodes 0 and 1 also point to root from earlier compression.

3. Step 3: Count elements directly pointing to root

   Elements 0,1,2,3,4,5 all point directly to the root after the final find(5) call due to path compression.

4. Final Answer:

   6 -> Option A

5. Quick Check:

   All nodes point directly to root after final find call [OK]

Hint: Count nodes updated by find calls for direct root pointers [OK]

Common Mistakes:

• Assuming all nodes point directly after union
• Ignoring path compression effect only on find calls
• Counting nodes without tracing parent updates