Path Compression in Union Find in DSA Python

Mental Model

Path compression makes finding the leader of a group faster by making every node on the path point directly to the leader.

Analogy: Imagine a family tree where each person points to their parent. Path compression is like updating everyone in the family line to point directly to the oldest ancestor, so you can find the root ancestor quickly next time.

Before path compression:
4 -> 3 -> 1 -> 1
↑
find(4) starts here

After path compression:
4 -> 1
3 -> 1
1 -> 1

Dry Run Walkthrough

Input: Union sets: union(1,2), union(3,4), union(2,4); then find(4)

Goal: Show how path compression updates the parent links to speed up future finds

Step 1: union(1,2) merges sets containing 1 and 2

parent: [0,1,1,3,4]  # 1 is parent of 2
rank: [0,1,0,0,0]

Why: We link 2 under 1 (ranks equal, rank[1] +=1)

Step 2: union(3,4) merges sets containing 3 and 4

parent: [0,1,1,3,3]  # 3 is parent of 4
rank: [0,1,0,1,0]

Why: 3 joins with 4 (ranks equal, rank[3] +=1)

Step 3: union(2,4) merges sets {1,2} and {3,4}

parent: [0,1,1,1,3]  # 3 under 1, 4 still ->3
rank: [0,2,0,1,0]

Why: find(2)=1, find(4)=3 (ranks 2 > 1), link 3->1, rank[1] remains 2. Chain: 4->3->1

Step 4: find(4): 4->3->1, compresses path

parent: [0,1,1,1,1]  # 4->1, 3->1
rank: [0,2,0,1,0]

Why: Recursive: parent[4]=find(3), parent[3]=find(1)=1; flattens to root

Result:

After find(4), 4 points directly to 1:
parent: [0,1,1,1,1]
Find(4) = 1
Future finds on 4 are now direct.

Annotated Code

DSA Python

class UnionFind:
    def __init__(self, size: int):
        self.parent = list(range(size + 1))
        self.rank = [0] * (size + 1)

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

uf = UnionFind(4)
uf.union(1, 2)
uf.union(3, 4)
uf.union(2, 4)
print(f"Find(4) = {uf.find(4)}")
print(f"Parent array after path compression: {uf.parent[1:]} " )

if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])

compress path by making x point directly to leader

rootX = self.find(x) rootY = self.find(y)

find leaders of x and y sets

if rootX != rootY:

only union if leaders differ

if self.rank[rootX] < self.rank[rootY]: self.parent[rootX] = rootY

attach smaller rank tree under bigger rank tree

elif self.rank[rootX] > self.rank[rootY]: self.parent[rootY] = rootX

attach smaller rank tree under bigger rank tree

else: self.parent[rootY] = rootX self.rank[rootX] += 1

if ranks equal, attach and increase rank

Output

Find(4) = 1

Parent array after path compression: [1, 1, 1, 1]

Complexity Analysis

Time: O(α(n)) per find or union operation, where α is the inverse Ackermann function, which is very slow growing and almost constant for all practical n, because path compression flattens the tree.

Space: O(n) for storing parent and rank arrays for n elements.

vs Alternative: Without path compression, find can be O(n) in worst case due to tall trees; path compression reduces this to almost O(1) amortized.

Edge Cases

Find on element that is its own leader

Returns element itself immediately without recursion

DSA Python

if self.parent[x] != x:

Union of elements already in the same set

No changes to parent or rank arrays

DSA Python

if rootX != rootY:

Union with rank tie

One root becomes parent and its rank increases by 1

DSA Python

else:
    self.parent[rootY] = rootX
    self.rank[rootX] += 1

When to Use This Pattern

When you see problems about grouping or connectivity with repeated queries to check if two items are connected, reach for Union Find with path compression because it efficiently merges groups and answers queries quickly.

Common Mistakes

Mistake: Not updating parent during find, missing path compression
Fix: Add parent[x] = find(parent[x]) to flatten the tree

Mistake: Union without checking ranks, causing tall trees
Fix: Use rank to attach smaller tree under bigger tree

Summary

Path compression speeds up finding the leader by making nodes point directly to the leader.

Use it when you need to repeatedly find and union groups efficiently.

The key insight is flattening the tree structure during find to make future finds faster.

Practice

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

easy

A. To delete elements from the set efficiently

B. To merge two sets without checking their roots

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

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

4. Quick Check:

   Path compression = speed up find [OK]

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

Common Mistakes:

• Confusing path compression with union operation
• Thinking it deletes elements
• Believing it sorts elements

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

easy

A. def find(x): parent[x] = x return x

B. def find(x): while parent[x] != x: x = parent[x] return x

C. def find(x): return x if parent[x] == x else find(parent[x])

D. def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x]

Solution

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

   def 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: Verify other options

   def find(x): while parent[x] != x: x = parent[x] return x uses iteration but no path compression update. def find(x): return x if parent[x] == x else find(parent[x]) lacks assignment to parent[x]. def find(x): parent[x] = x return x incorrectly resets parent[x] always.

3. Final Answer:

   def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] -> Option D

4. Quick Check:

   Path compression requires assignment in find [OK]

Hint: Path compression assigns parent[x] during find [OK]

Common Mistakes:

• Missing assignment to parent[x]
• Using iteration without updating parents
• Resetting parent[x] incorrectly

3. Given the following code snippet with path compression, what will be the output of print(parent) after the operations?

parent = [0, 1, 2, 3, 4]
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        parent[rootB] = rootA

union(1, 2)
union(2, 3)
find(3)
print(parent)

medium

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

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

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

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

Solution

1. Step 1: Perform unions and track parents

   union(1,2): parent[2] = 1; union(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. Final parent array: [0,1,1,1,4]

3. Final Answer:

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

4. Quick Check:

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

Hint: Trace unions then find with path compression [OK]

Common Mistakes:

• Not updating parent during find
• Confusing root assignments
• Ignoring path compression effect

4. Identify the bug in the following find function that is supposed to implement path compression:

def find(x):
    if parent[x] == x:
        return x
    else:
        find(parent[x])

medium

A. Incorrect base case condition

B. Missing return statement in the else branch

C. Parent array is not initialized

D. Using recursion instead of iteration

Solution

1. Step 1: Check the else branch

   The else branch calls find(parent[x]) but does not return its result, so the function returns None.

2. Step 2: Understand path compression requirement

   Without returning the recursive call result, path compression and correct root finding fail.

3. Final Answer:

   Missing return statement in the else branch -> Option B

4. Quick Check:

   Return recursive find result [OK]

Hint: Always return recursive call in find [OK]

Common Mistakes:

• Forgetting return in recursion
• Misunderstanding base case
• Assuming iteration is required

5. You have a Union Find structure with 5 elements (0 to 4). After performing union(0,1), union(1,2), and union(3,4), you call find(2) and find(4) with path compression. Which of the following statements is true about the parent array after these operations?

hard

A. Elements 0, 1, and 2 will have the same root, and 3 and 4 will have the same root, with path compression applied

B. All elements will have different roots because path compression does not merge sets

C. Elements 0 and 4 will share the same root after path compression

D. Path compression will cause all elements to point to element 0

Solution

1. Step 1: Analyze unions

   union(0,1) and union(1,2) merge 0,1,2 into one set. union(3,4) merges 3 and 4 into another set.

2. Step 2: Effect of find with path compression

   find(2) compresses path so 2 points directly to root of set {0,1,2}. find(4) compresses path so 4 points directly to root of set {3,4}.

3. Step 3: Confirm roots and parent array

   Sets remain separate; 0,1,2 share root; 3,4 share root; path compression flattens trees.

4. Final Answer:

   Elements 0, 1, and 2 will have the same root, and 3 and 4 will have the same root, with path compression applied -> Option A

5. Quick Check:

   Unions merge sets; path compression flattens but does not merge sets [OK]

Hint: Unions merge sets; path compression flattens trees only [OK]

Common Mistakes:

• Thinking path compression merges sets
• Assuming all elements share one root
• Confusing union and find roles