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

Concept Flow - Path Compression in Union Find

Start: Find(x)

↓

Is parent[x

↓

Return x

↓

Set parent[x

↓

Return root

Find the root of x. If x is not root, recursively find root and update x's parent to root for faster future queries.

Execution Sample

DSA C++

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

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

Execution Table

Step	Operation	Node x	parent[x] before	Recursive Call	parent[x] after	Visual State
1	Call find(4)	4	3	find(3)	?	4->3->2->2
2	Call find(3)	3	2	find(2)	?	4->3->2->2
3	Call find(2)	2	2	No recursion (root)	2	4->3->2->2
4	Return from find(2)	2	2	None	2	4->3->2->2
5	Set parent[3] = 2	3	2	None	2	4->3->2->2
6	Return from find(3)	3	2	None	2	4->3->2->2
7	Set parent[4] = 2	4	3	None	2	4->2->2->2
8	Return from find(4)	4	2	None	2	4->2->2->2
9	Final parent array	-	-	-	-	parent = [0,1,2,2,2]

💡 Recursion ends when node is its own parent (root). Path compression updates parents to root.

Variable Tracker

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

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 root to shorten the path, as shown in steps 5 and 7 in the execution_table.

What stops the recursion in find function?

Recursion stops when parent[x] == x, meaning x is the root, as seen in step 3 where find(2) returns immediately.

How does path compression improve future find calls?

By making nodes point directly to the root, future find calls reach the root faster, reducing the tree height, as shown by parent[4] changing from 3 to 2.

Visual Quiz - 3 Questions

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

A 2

B 3

C 4

D 1

💡 Hint

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

At which step does the recursion stop because the node is its own parent?

A Step 5

B Step 1

C Step 3

D Step 7

💡 Hint

Look for the step where 'No recursion (root)' is noted in the Recursive Call column.

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

A 4 would become root

B 4 would point directly to 2 after compression

C 3 would remain pointing to 4, no change

D 3 would point to itself

💡 Hint

Path compression always updates nodes to point directly to root, as shown in steps 5 and 7.

Concept Snapshot

Path Compression in Union Find:
- Used in find(x) to flatten tree.
- If parent[x] != x, recursively find root.
- Set parent[x] = root to shorten path.
- Speeds up future find operations.
- Key for efficient union-find performance.

Full Transcript

Path Compression in Union Find helps speed up the find operation by making every node on the path point directly to the root. The find function checks if a node is its own parent. If not, it recursively finds the root and updates the node's parent to the root. This flattens the structure, making future finds faster. The execution trace shows how parent pointers change step-by-step, with recursion stopping at the root node. Key moments clarify why parent updates happen after recursion and how this improves efficiency.

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 making nodes point directly to the root

C. To initialize the parent array

D. To count the number of connected components

Solution

1. Step 1: Understand the find operation

   The find operation locates the root parent of a node in Union Find.

2. Step 2: Role of path compression

   Path compression updates nodes along the path to point directly to the root, reducing future search time.

3. Final Answer:

   To speed up the find operation by making nodes point directly to the root -> Option B

4. Quick Check:

   Path compression optimizes find = To speed up the find operation by making nodes point directly to the root [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 syntax for the find function with path compression in C++?

easy

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

B. int find(int x) { while(parent[x] != x) x = parent[x]; return x; }

C. int find(int x) { return parent[x]; }

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

Solution

1. Step 1: Identify path compression usage

   Path compression updates parent[x] during recursion to root.

2. Step 2: Check each option

   int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } updates parent[x] with recursive call result, implementing path compression correctly.

3. Final Answer:

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

4. Quick Check:

   Path compression requires assignment in recursion = int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } [OK]

Hint: Look for recursive assignment to parent[x] in find [OK]

Common Mistakes:

• Missing assignment to parent[x] for compression
• Using iterative find without compression
• Returning parent[x] without recursion

3. Consider the following code snippet using Union Find with path compression:

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

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

void unionSet(int a, int b) {
  int rootA = find(a);
  int rootB = find(b);
  if(rootA != rootB) parent[rootB] = rootA;
}

unionSet(1, 2);
unionSet(2, 3);
find(3);

What is the state of the parent array after these operations?

medium

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

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

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

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

Solution

1. Step 1: Perform unions

   unionSet(1,2): parent[2] = 1; unionSet(2,3): parent[3] = find(2) = 1, so parent[3] = 1.

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

   find(3) updates parent[3] to root 1 (already 1), so no change. parent array: [0,1,1,1,4]

3. Final Answer:

   [0, 1, 1, 1, 4] -> Option D

4. Quick Check:

   Parents after unions and compression = [0,1,1,1,4] [OK]

Hint: Trace unions first, then apply find with compression [OK]

Common Mistakes:

• Not updating parent of 3 during union
• Ignoring path compression effect in find
• Confusing indices and values in parent array

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

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

What is the bug in this code?

medium

A. It does not update parent[x] during recursion for compression

B. It uses == instead of != in the base case

C. It returns parent[x] instead of x

D. It causes infinite recursion

Solution

1. Step 1: Analyze recursion call

   The recursive call find(parent[x]) is made but its result is not assigned back to parent[x].

2. Step 2: Effect on path compression

   Without assignment, parent[x] remains unchanged, so path compression does not happen.

3. Final Answer:

   It does not update parent[x] during recursion for compression -> Option A

4. Quick Check:

   Missing assignment breaks path compression = It does not update parent[x] during recursion for compression [OK]

Hint: Always assign recursion result to parent[x] for compression [OK]

Common Mistakes:

• Thinking base case condition is wrong
• Assuming return value is incorrect
• Believing it causes infinite recursion

5. You have a Union Find structure with 6 elements (0 to 5). Initially, each element is its own parent. You perform these operations:

unionSet(0, 1);
unionSet(1, 2);
unionSet(3, 4);
unionSet(4, 5);
find(2);
find(5);
unionSet(2, 5);
find(5);

After all operations, what is the parent array state assuming path compression is used in find?

hard

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

B. [0, 0, 0, 3, 3, 3]

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

D. [0, 0, 1, 3, 3, 0]

Solution

1. Step 1: Perform initial unions

   unionSet(0,1): parent[1]=0; unionSet(1,2): parent[2]=find(1)=0; unionSet(3,4): parent[4]=3; unionSet(4,5): parent[5]=find(4)=3;

2. Step 2: Apply finds with path compression

   find(2): compresses path for 2 to 0 (already 0); find(5): compresses path for 5 to 3 (already 3); unionSet(2,5): parent[3]=find(2)=0; find(5): compresses path for 5 to 0, so parent[5]=0;

3. Step 3: Final parent array

   parent[0]=0, parent[1]=0, parent[2]=0, parent[3]=0 (updated), parent[4]=3, parent[5]=0 (compressed)

4. Final Answer:

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

5. Quick Check:

   After unions and compression, parent array = [0, 0, 0, 0, 3, 0] [OK]

Hint: Track unions then compress paths after finds [OK]

Common Mistakes:

• Not updating parent of 3 during unionSet(2,5)
• Ignoring path compression effect on 5 after last find
• Mixing parent indices and values