Finally, we will connect the ultimate parent with a smaller rank to the other ultimate parent with a larger rank. But if the ranks are equal, we can connect any parent to the other parent and we will increase the rank by one for the parent node to whom we have connected the other one.

Let’s understand it further using the below example.

Given the edges of a graph are: {{1,2}, {2,3}, {4,5}, {6,7}, {5,6}}

After applying the union by rank function to every edge the graph and the arrays will look like the following:

Observation 1:

If we carefully observe, we are only concerned about the ultimate parent but not the immediate parent.

Let’s see why we need to find the ultimate parents.

After union by rank operations, if we are asked (refer to the above picture) if node 5 and node 7 belong to the same component or not, the answer must be yes. If we carefully look at their immediate parents, they are not the same but if we consider their ultimate parents they are the same i.e. node 4. So, we can determine the answer by considering the ultimate parent. That is why we need to find the ultimate parent.

So, here comes the findPar() function which will help us to find the ultimate parent for a particular node.

findPar() function:

This function actually takes a single node as an argument and finds the ultimate parent for each node.

Observation 2:

Now, if we try to find the ultimate parent(typically using recursion) of each query separately, it will end up taking O(logN) time complexity for each case. But we want the operation to be done in a constant time. This is where the path compression technique comes in.

Using the path compression technique we can reduce the time complexity nearly to constant time. It is discussed later on why the time complexity actually reduces.

What is path compression?

Basically, connecting each node in a particular path to its ultimate parent refers to path compression. Let’s understand it using the following illustration:

How the time complexity reduces:

Before path compression, if we had tried to find the ultimate parent for node 4, we had to traverse all the way back to node 1 which is basically the height of size logN. But after path compression, we can easily access the ultimate parent with a single step. Thus the traversal reduces and as a result the time complexity also reduces.