Path Compression in Find Operations

In our last lesson, we established the fundamentals of the Union-Find data structure, understanding its representation as a forest of trees and implementing its core find and union operations. We also identified a critical weakness in our naive approach: the potential for trees to become tall and "stringy," leading to find operations that take linear time, O(N).

Today, we will directly address this inefficiency. Your goal is to implement the path compression optimization in the find operation. This elegant and powerful technique dramatically flattens the trees within our Union-Find structure, drastically improving its performance. For a programmer focused on interview-level efficiency, understanding and being able to implement path compression is non-negotiable.

The Problem with Long Paths

Let's revisit the issue from last time. A sequence of unions like union(1, 2), union(2, 3), union(3, 4) could create a chain: 1 <- 2 <- 3 <- 4. A call to find(1) would require traversing three parent pointers to reach the root, 4. As the number of elements N grows, this path could grow to length N-1, making find an O(N) operation.

Path compression offers a simple yet profound solution: if we're going to the trouble of traversing a path to find the root, why not use that information to make future searches faster?

The Core Idea: Flattening the Tree

Path compression is an optimization applied during the find operation. The principle is straightforward: after we find the ultimate root of a given node, we make every node along the path we traversed point directly to that root.

Consider the tree on the left in the image below. To find the root of node 7, we must traverse the path 7 → 5 → 3 → 2 → 1. The root is 1.

After applying path compression during this find(7) operation, we restructure the tree. Nodes 7, 5, and 3 are all made direct children of the root, 1. Any subsequent find operation on these nodes will now take only a single step to reach the root. This is a "lazy" optimization—we only flatten paths as we traverse them.

The following video provides an excellent visual walkthrough of this concept. Pay close attention to how a tall, chain-like tree is compressed into a flat, star-shaped one.

Implementing Path Compression

The beauty of path compression lies in its implementation. A small modification to our recursive find function is all it takes.

Recall the naive recursive find_set from the previous lesson:

int find_set(int v) {
    if (v == parent[v])
        return v;
    return find_set(parent[v]);
}

This function finds the root but does nothing to alter the tree structure.

To implement path compression, we modify the recursive step. As the recursion unwinds, we assign the returned root to the parent of each node along the path.

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]); // The magic happens here!
}

Let's break down that crucial line return parent[v] = find_set(parent[v]);:

1. The recursive call find_set(parent[v]) continues up the tree until it finds the ultimate root.
2. This root is returned back down the call stack.
3. At each level of the unwinding recursion, the assignment parent[v] = ... sets the parent of the current node v directly to the ultimate root that was just found.
4. Finally, the root is returned to the original caller.

The following resource provides a concise explanation and the code for this optimized find_set function.

A Note on Performance

With just this single-line change, the performance of our data structure improves dramatically. While a formal proof is complex, the practical result is that the amortized time complexity of the find operation becomes nearly constant.

The complexity is formally described by the Inverse Ackermann function, written as $\alpha (N)$. This function grows so incredibly slowly that for any input size you would ever encounter in practice (even numbers far larger than the number of atoms in the universe), its value is no greater than 5. Therefore, for all practical purposes in a coding interview context, you can consider the optimized find operation to be O(1) on average.

This video from Tushar Roy provides another clear walkthrough of the implementation and touches on this performance implication.

Conclusion

In this lesson, we tackled the primary performance bottleneck of the naive Union-Find implementation. By adding the path compression optimization, we've transformed a potentially linear-time operation into one that is practically constant time.

Key Takeaways:

• Motivation: Path compression solves the problem of tall, unbalanced trees that slow down find operations.
• Mechanism: During a find operation, it makes every node on the path from the element to the root point directly to that root.
• Implementation: This is elegantly achieved with a one-line modification in the recursive find function: parent[v] = find_set(parent[v]).
• Performance: Path compression reduces the amortized time complexity of find to nearly constant, denoted by the very slowly growing Inverse Ackermann function, $\alpha (N)$.

You are now equipped with the first of two critical optimizations for the Union-Find data structure. While path compression optimizes find, our next lesson will focus on an optimization for the union operation: union by rank/size. When used together, these two techniques create an exceptionally efficient data structure for solving a wide range of connectivity problems.