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 to flatten the structure.

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 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)	TBD	4->3->1->1
2	Call find(3)	3	1	find(1)	TBD	4->3->1->1
3	Call find(1)	1	1	No recursion	1	4->3->1->1
4	Set parent[3] = 1	3	1	Return 1	1	4->3->1->1
5	Set parent[4] = 1	4	3	Return 1	1	4->1->1->1
6	Return root for find(4)	4	1	Return 1	1	4->1->1->1
7	Final parent array	-	-	-	-	parent = [0,1,2,1,1]

💡 Recursion ends when node is its own parent; path compression updates intermediate parents to root.

Variable Tracker

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

Key Moments - 3 Insights

Why does find(4) call find(3) before returning?

Because parent[4] is 3, not 4 itself, so we must find the root of 3 first (see execution_table step 1 and 2).

How does path compression update parent pointers?

After finding the root, each node on the path sets its parent directly to the root (see steps 4 and 5 in execution_table).

Why does recursion stop when parent[x] == x?

Because that means x is the root of its set, so no further recursion is needed (step 3 in execution_table).

Visual Quiz - 3 Questions

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

A 3

B 4

C 1

D 0

💡 Hint

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

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

A Step 2

B Step 3

C Step 1

D Step 5

💡 Hint

Look for 'No recursion' in the Recursive Call column in execution_table.

If parent[4] was initially 4 (itself), what would happen when find(4) is called?

A No recursion, find returns 4 immediately

B Recursion would continue deeper

C parent[4] would be updated to 1

D An error would occur

💡 Hint

Refer to the condition 'parent[x] == x' stopping recursion in concept_flow.

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 speed future finds.
- Reduces tree height, improves efficiency.
- Key for almost O(1) amortized find operations.

Full Transcript

Path Compression in Union Find improves the find operation by making each 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 that root. This flattens the structure, making future finds faster. The execution trace shows find(4) calling find(3), which calls find(1), the root. Then parent pointers of 3 and 4 are updated to 1. This process stops recursion when a node is its own parent. The variable tracker shows how parent pointers change step-by-step. Key moments clarify why recursion happens and how path compression updates parents. The quiz tests understanding of parent updates and recursion stopping conditions.

Practice

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

easy

A. To initialize the parent array

B. To merge two sets by size

C. To count the number of connected components

D. To speed up the find operation by making nodes point directly to the root

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 makes all nodes on the path point directly to the root, speeding up future find calls.

3. Final Answer:

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

4. Quick Check:

   Path compression optimizes find = C [OK]

Hint: Path compression flattens tree for faster find [OK]

Common Mistakes:

• Confusing path compression with union by size
• Thinking it initializes the structure
• Believing it counts components

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

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

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

Solution

1. Step 1: Identify path compression in code

   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 find 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 B

4. Quick Check:

   Path compression updates parent recursively = A [OK]

Hint: Look for parent update inside find recursion [OK]

Common Mistakes:

• Using loop without updating parent (Option B)
• Not updating parent during recursion (Option C)
• Resetting parent incorrectly (Option D)

3. Given the following Union Find structure with parent = [0, 0, 1, 2, 3], what will be the parent array after calling find(4) with path compression?

medium

A. [0, 0, 0, 0, 0]

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

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

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

Solution

1. Step 1: Trace find(4) path

   4's parent is 3, 3's parent is 2, 2's parent is 1, 1's parent is 0, which is root.

2. Step 2: Apply path compression

   All nodes on path (4,3,2,1) update parent to root 0 (parent[1] already 0). parent[2]=0, parent[3]=0, parent[4]=0. So parent array becomes [0,0,0,0,0].

3. Final Answer:

   [0, 0, 0, 0, 0] -> Option A

4. Quick Check:

   Path compression sets parent[4] = 0 = A [OK]

Hint: Update all parents on path to root after find [OK]

Common Mistakes:

• Only updating parent[4] to root (Option B)
• Not updating any parent (Option C)
• Updating wrong parents (Option D)

4. Identify the bug in this find function with path compression:

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

medium

A. No bug, code is correct

B. Incorrect base case condition

C. Missing return value from recursive call before assignment

D. Parent update should be after return

Solution

1. Step 1: Analyze recursive call

   The recursive call find(parent[x]) is made but its return value is ignored.

2. Step 2: Check parent update

   Parent update uses parent[parent[x]] instead of the root returned by recursion, so path compression fails.

3. Final Answer:

   Missing return value from recursive call before assignment -> Option C

4. Quick Check:

   Return value must be assigned to parent[x] = D [OK]

Hint: Assign recursive find result to parent[x] for compression [OK]

Common Mistakes:

• Ignoring recursive return value
• Updating parent incorrectly
• Misunderstanding base case

5. You have a Union Find with 5 elements and parent = [0, 0, 1, 2, 3]. After calling union(4, 0) and then find(4) with path compression, what is the final parent array?

hard

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

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

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

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

Solution

1. Step 1: Perform union(4, 0)

   Find roots: root(4) = 4 (chain 4->3->2->1->0), root(0) = 0. Since roots differ, link root(4) to root(0). So parent[4] = 0. Updated parent = [0, 0, 1, 2, 0].

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

   Path: 4 -> 0. Since 0 is root, parent[4] already 0, no further updates. Final parent = [0, 0, 1, 2, 0].

3. Final Answer:

   [0, 0, 1, 2, 0] -> Option A

4. Quick Check:

   Union links 4 to 0, find compresses path = A [OK]

Hint: Union links roots, find compresses path to root [OK]

Common Mistakes:

• Incorrectly linking assuming same root (Option C)
• Wrong union target (Option B)
• Incomplete path compression (Option D)