Path Compression in Union Find in DSA Java - 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

Path Compression flattens the tree by making each node point directly to the root during find, speeding up future finds.

Execution Sample

DSA Java

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	Call find(4)	4	3	find(3)	TBD	Initial parent array: [0,1,2,1,3,5]
2	Call find(3)	3	1	find(1)	TBD	parent[4] points to 3
3	Call find(1)	1	1	No recursion	1	parent[3] points to 1
4	Return from find(1)	1	1	-	1	parent[1] is root
5	Set parent[3] = 1	3	1	-	1	Path compressed: 3 → 1
6	Return from find(3)	3	1	-	1	parent[3] updated
7	Set parent[4] = 1	4	3	-	1	Path compressed: 4 → 1
8	Return from find(4)	4	1	-	1	parent[4] updated
9	Final parent array	-	-	-	-	[0,1,2,1,1,5]

💡 Recursion ends when parent[x] == x (root found), then path compression updates parent pointers on return.

Variable Tracker

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

Key Moments - 3 Insights

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

Because after finding the root, we set parent[x] directly to the root to flatten the tree, as shown in steps 5 and 7 in the execution_table.

What stops the recursion in the find function?

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

How does path compression improve future find operations?

By making nodes point directly to the root, future finds reach the root faster, reducing tree height, demonstrated by parent[4] changing from 3 to 1.

Visual Quiz - 3 Questions

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

A 4

B 3

C 1

D 0

💡 Hint

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

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

A Step 2

B Step 3

C Step 5

D Step 7

💡 Hint

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

If parent[3] was initially 2 instead of 1, how would the visual state change after step 5?

A parent[3] would point to 2, no path compression yet

B parent[3] would point to 1 directly

C parent[3] would point to 3 itself

D parent[3] would be null

💡 Hint

Refer to how path compression updates parent pointers only after recursive find returns.

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 found.
- Speeds up future find operations by shortening paths.
- Key for efficient Union-Find performance.

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 checks if a node is its own parent (root). If not, it recursively finds the root and updates the node's parent to this root. This flattens the tree structure, reducing the time for future finds. The execution trace shows find(4) calling find(3), which calls find(1), the root. On returning, parent[3] and parent[4] are updated to 1, compressing the path. This process stops recursion when a node is its own parent. Path compression is essential for efficient Union-Find operations.

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 flattening the tree structure

C. To initialize the parent array

D. To count the number of connected components

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 structure -> Option B

4. Quick Check:

   Path compression = flatten tree for faster find [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 Java method signature for the find function implementing path compression in Union Find?

easy

A. public int find(int x)

B. public void find(int x)

C. public boolean find(int x)

D. public int find()"

Solution

1. Step 1: Understand the return type of find

   The find method returns the representative (root) of the set containing element x, so it returns an integer.

2. Step 2: Check method parameters

   The method must accept the element x as input to find its root.

3. Final Answer:

   public int find(int x) -> Option A

4. Quick Check:

   find returns root index as int [OK]

Hint: find returns int root and takes int parameter [OK]

Common Mistakes:

• Using void return type for find
• Missing parameter for element to find
• Returning boolean instead of int

3. Consider the following Java code snippet implementing path compression in Union Find:

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

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

System.out.println(find(4));
System.out.println(Arrays.toString(parent));

What is the output?

medium

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

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

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

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

Solution

1. Step 1: Trace find(4) call with path compression

   parent[4]=3 -> find(3); parent[3]=2 -> find(2); parent[2]=1 -> find(1); parent[1]=0 -> find(0)=0 (base); parent[1]=0; parent[2]=0; parent[3]=0; parent[4]=0. Returns 0.

2. Step 2: Update parent array after path compression

   Entire path flattens: parent = [0, 0, 0, 0, 0].

3. Final Answer:

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

4. Quick Check:

   find(4) = 0, all path nodes point to root 0 [OK]

Hint: Path compression flattens entire path to root [OK]

Common Mistakes:

• Thinking only leaf updates (partial compression)
• Expecting no change in parent array
• Misreading recursion depth or base case

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

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

What is the bug and how to fix it?

medium

A. Missing path compression assignment; fix by adding parent[x] = find(parent[x]);

B. Incorrect base case; fix by changing parent[x] == x to parent[x] != x

C. Wrong return type; fix by changing return type to void

D. No bug; code is correct

Solution

1. Step 1: Identify missing path compression step

   The method recursively finds the root but does not update parent[x] to root, so no path compression happens.

2. Step 2: Fix by assigning compressed parent

   Adding parent[x] = find(parent[x]); before returning compresses the path.

3. Final Answer:

   Missing path compression assignment; fix by adding parent[x] = find(parent[x]); -> Option A

4. Quick Check:

   Assign parent[x] = find(parent[x]) for compression [OK]

Hint: Always assign parent[x] = find(parent[x]) to compress path [OK]

Common Mistakes:

• Forgetting to update parent[x]
• Changing base case incorrectly
• Returning void instead of int

5. Given a Union Find structure with parent = {0, 0, 1, 2, 4, 5} and rank = {0, 1, 2, 3, 4, 5}, after performing union(4, 5) and then find(5) with path compression, what will be the updated parent array?

hard

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

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

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

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

Solution

1. Step 1: Perform union(4, 5) by rank

   Ranks: rank[4]=4, rank[5]=5. Since rank[5] > rank[4], parent[4] = 5. But ranks given are increasing, so actually rank[5] is highest, so parent[4] = 5.

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

   find(5) returns 5 (root). Path compression updates parent of 5 to itself (no change). But parent[4] points to 5, so parent array is [0,0,1,2,5,5].

3. Step 3: Check options

   [0, 0, 1, 2, 4, 4] shows parent[5] = 4, which contradicts union by rank. [0, 0, 1, 2, 3, 4] no change. [0, 0, 1, 2, 3, 3] parent[5]=3 incorrect. [0, 0, 1, 2, 5, 5] parent[4]=5 and parent[5]=5 matches expected.

4. Final Answer:

   [0, 0, 1, 2, 5, 5] -> Option D

5. Quick Check:

   Union by rank sets parent of lower rank to higher [OK]

Hint: Union by rank attaches lower rank root to higher rank root [OK]

Common Mistakes:

• Confusing which parent to update in union
• Ignoring rank comparison
• Assuming parent array unchanged after union