Finding your roots

I tried working on the Algorithms I course on Coursera a while back and I had no idea what was going on so I never continued with it. I decided to give it another try now that I've read up a little on algorithms. It's still using a lot of my brain cells but I am slowly making my way through it. 

Learning about Quick-unions in Java(from the course)

Java seems almost identical to C#. I've forgotten most of what I've learnt about C# but, there's enough in this brain for me to read this. I had such a tough time understanding the root method. I wrote it out in my notebook and worked through it to figure out how it functions and I am amazed! That line is so simple yet complex. And it reminded me of a binary tree LeetCode challenge I was trying to work on with my colleagues some time ago. I had no idea what binary trees even were at that point. The challenge involved finding roots and tree heights. This little while loop here would have been perfect for it!

Explanation to self:

• In the constructor(public QuickUnionUF(int N)) of this class, an integer was taken in as an argument and used to determine the length of the array. The array's values were then initialised with a for loop. So they were consecutive numbers(with an increment of 1 on each iteration) starting at 0 and ending when the length of the array matched up with the input.

e.g. QuickUnionUF(5) would create the array: [0, 1, 2, 3, 4] where index matches the value of the item in the array. It's been set up this way so that the index is the node in the tree and the item represents what the node is linked to. When the array is first initialised, the nodes are not connected and they are all their own parent.

• id[0] = 0 
• id[1] = 1
• id[2] = 2
• id[3] = 3
• id[4] = 4         

• root(int i) : This method is magic. It traces the the roots of each node. Initially the condition in the while loop evaluates to true as all nodes are their own parents. But as unions are made, this will change.

After union(1,0), union(4,2) and union(4,3)

From Coursera

Following this code, let's say we want to find the root of the node 2(remember: this is the index of the array, not the value). So that's:

We call root(2)  

>>> Check condition. id[2] = 4, therefore 2 != id[2]  

>>> We enter the while loop  

>>> The code says to to assign id[2] to i. So i = id[2] = 4  

>>>>>>>>>>>>End iteration>>>>>>>>>>>>  

>>> Next iteration. Check condition. i= 4. 4 != id[4], as id[4] = 3  

>>> We enter the while loop again  

>>> The code says to assign id[4] to i. i = id[4] = 3  

>>>>>>>>>>>>End iteration>>>>>>>>>>>>  

>>> Next iteration. Check condition. i = 3. 3==3. Condition evaluates to false.   

>>> Exit while loop  

>>> Return i, which is 3. The root of the node 2 is the node 3.

root(2)

• connected(int p, int q): I think this is pretty easy to understand. When this function is called, it returns a boolean. It calls the method root to find the root of p and q. If they are the same, the nodes are connected and True is returned. 
• union(int p, int q):  This method is also fairly straightforward. It joins nodes so that they have the same root. It finds the root of p and q and assigns the root of p to the root of q.