Path Compression in Union Find in DSA Javascript - Execution Trace

Concept Flow - Path Compression in Union Find

Start: Find(x)

↓

Is parent[x

↓

Return x

↓

Set parent[x

↓

Return root

This flow shows how path compression works by recursively finding the root and updating each node's parent to point directly to the root.

Execution Sample

DSA Javascript

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

// Example: find(3) with parent = [0,1,1,2,4]

This code finds the root of element x and compresses the path by making all nodes on the path point directly to the root.

Execution Table

Step	Operation	Current Node (x)	Parent Array	Pointer Changes	Visual State
1	Call find(3)	3	[0,1,1,2,4]	None yet	3 → 2 → 1 (root)
2	Check parent[3] != 3	3	[0,1,1,2,4]	Yes, parent[3] = 2	3 → 2 → 1
3	Call find(2)	2	[0,1,1,2,4]	None yet	2 → 1 (root)
4	Check parent[2] != 2	2	[0,1,1,2,4]	Yes, parent[2] = 1	2 → 1
5	Call find(1)	1	[0,1,1,2,4]	None yet	1 → 1 (root)
6	Check parent[1] != 1	1	[0,1,1,2,4]	No	1 is root
7	Return 1 to find(2)	2	[0,1,1,2,4]	parent[2] updated to 1	2 → 1
8	Return 1 to find(3)	3	[0,1,1,1,4]	parent[3] updated to 1	3 → 1
9	Final parent array	-	[0,1,1,1,4]	parent[3] and parent[2] point to 1	0→0,1→1,2→1,3→1,4→4

💡 Recursion ends when parent[x] == x (root found), path compressed by updating parents.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	Final
parent	[0,1,1,2,4]	[0,1,1,2,4]	[0,1,1,1,4]	[0,1,1,1,4]	[0,1,1,1,4]
x (current node)	3	3	2	3	-

Key Moments - 3 Insights

Why do we update parent[x] during the recursive return?

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

What stops the recursion in find(x)?

Recursion stops when parent[x] == x, meaning x is the root, as shown in step 6 where parent[1] == 1.

Why does path compression speed up future finds?

Because it makes nodes point directly to the root, reducing the path length, as seen when parent[3] and parent[2] are updated to 1 in step 9.

Visual Quiz - 3 Questions

Look at the execution_table, what is the parent of node 3 after step 8?

A 3

B 1

C 2

D 4

💡 Hint

Check the 'Pointer Changes' and 'Parent Array' columns at step 8.

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

A Step 2

B Step 4

C Step 6

D Step 9

💡 Hint

Look for the step where 'Check parent[x] != x' is false.

If parent[2] was initially 3 instead of 1, how would the parent of node 3 change after find(3)?

A It would remain 2

B It would become 1

C It would become 3

D It would become 0

💡 Hint

Consider the recursive calls and path compression updating parents to the root.

Concept Snapshot

Path Compression in Union Find:
- Used in find(x) to flatten tree.
- Recursively find root parent.
- Update parent[x] to root on return.
- Speeds up future find operations.
- Keeps tree shallow for efficiency.

Full Transcript

Path Compression in Union Find works by recursively finding the root of a node and updating each node's parent pointer along the path to point directly to the root. This flattens the structure, making future find operations faster. The recursion stops when a node is its own parent, indicating the root. During the return phase of recursion, each node's parent is updated to the root, compressing the path. This process reduces the height of the tree and improves efficiency of union-find operations.

Practice

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

easy

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

B. To merge two sets without checking their roots

C. To initialize the parent array with default values

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 A

4. Quick Check:

   Path compression = flatten tree = faster find [OK]

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

Common Mistakes:

• Confusing path compression with union by rank
• Thinking it merges sets without root checks
• Believing it initializes data structures

2. Which of the following is the correct syntax for the find function with path compression in JavaScript?

easy

A. function find(x) { if (parent[x] === x) return x; else return find(parent[x]); }

B. function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; }

C. function find(x) { while (parent[x] !== x) x = parent[x]; return x; }

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

Solution

1. Step 1: Identify path compression in the code

   function find(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: Compare other options

   function find(x) { while (parent[x] !== x) x = parent[x]; return x; } uses iteration but no path compression. function find(x) { if (parent[x] === x) return x; else return find(parent[x]); } uses recursion but no assignment to parent[x]. function find(x) { parent[x] = x; return x; } resets parent incorrectly.

3. Final Answer:

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

4. Quick Check:

   Path compression requires parent update = function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } [OK]

Hint: Look for parent update inside find for path compression [OK]

Common Mistakes:

• Missing parent update for path compression
• Using iteration without compression
• Resetting parent incorrectly

3. Given the following code snippet, what will be the output of console.log(parent) after calling find(3)?

let parent = [0, 0, 1, 2, 4];
function find(x) {
  if (parent[x] !== x) parent[x] = find(parent[x]);
  return parent[x];
}
find(3);
console.log(parent);

medium

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

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

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

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

Solution

1. Step 1: Trace the find(3) call

   find(3) checks parent[3] = 2, not 3, so calls find(2). find(2) checks parent[2] = 1, not 2, so calls find(1). find(1) checks parent[1] = 0, not 1, so calls find(0). find(0) returns 0 since parent[0] = 0.

2. Step 2: Apply path compression updates

   parent[1] = 0, parent[2] = 0, parent[3] = 0 after recursion. But initial array was [0,0,1,2,4]. After updates, parent becomes [0,0,0,0,4]. However, the code only updates parent[x] during recursion. The first call updates parent[3] = find(2) = 0, parent[2] = find(1) = 0, parent[1] = find(0) = 0. So final parent array is [0,0,0,0,4].

3. Final Answer:

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

4. Quick Check:

   Path compression sets parents to root = [0,0,0,0,4] [OK]

Hint: Follow recursion and update parents to root [OK]

Common Mistakes:

• Not updating all parents during recursion
• Confusing parent indices
• Assuming no change after find

4. Identify the bug in the following find function implementing path compression:

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

medium

A. Function should use iteration instead of recursion

B. Incorrect base condition for recursion

C. Parent array is not updated for path compression

D. Missing return statement in the else branch

Solution

1. Step 1: Check the recursive calls and returns

   The else branch calls find(parent[x]) but does not return its result, so the function returns undefined for non-root nodes.

2. Step 2: Confirm missing return causes bug

   Without returning the recursive call, the function fails to return the root, breaking the find operation.

3. Final Answer:

   Missing return statement in the else branch -> Option D

4. Quick Check:

   Recursive calls must return values [OK]

Hint: Always return recursive find calls [OK]

Common Mistakes:

• Forgetting to return recursive call result
• Misunderstanding base case
• Thinking iteration is required

5. You have a Union Find structure with parent = [0, 0, 2, 2, 4] and rank = [0, 1, 0, 0, 0]. After performing union(3, 4) and then find(3), what will be the updated parent array assuming path compression is applied in find?

hard

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

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

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

D. [0, 0, 2, 4, 4]

Solution

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

   Find roots: find(3) = 2, find(4) = 4. Since rank[2] = 0 and rank[4] = 0, attach 3's root (2) to 4. So parent[2] = 4.

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

   find(3) calls find(2), which calls find(4). find(4) returns 4. Path compression sets parent[2] = 4 and parent[3] = parent[2] = 4.

3. Final Answer:

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

4. Quick Check:

   Union attaches root, find compresses path [OK]

Hint: Union attaches root; find compresses path to root [OK]

Common Mistakes:

• Not updating parent after union
• Ignoring path compression updates
• Confusing rank usage