little help to understand this code

[jasleen90]

I found this code on internet which I was unable to understand
Please help I am a beginner but I really want to understand this

struct node
{
node(int i, node * l =NULL, node * r=NULL): id(i), left(l), right(r) {}; /*wats
dis ":",meaning*/
int id;
node * left;
node * right;
};

bool FindNode(node * root, int id, std::vector& vec)// again can't get it
{
if (root == NULL)
return false;
else if(root->id == id)
{
vec.push_back(id); //???
return true;
}
else if ( FindNode( root->left, id, vec)) //???
{
vec.push_back(root->id);//??
return true;
}
else if ( FindNode(root->right, id, vec))
{
vec.push_back(root->id);
return true;
}
else
return false;

};


Please explain this code in simple terms
bool FindCommonAncestor( node * root, int n1, int n2, int & anc)
{
std::vector v1, v2;
if (FindNode(root, n1, v1) && FindNode(root, n2, v2))
{
//has common;

int anc;

while (!v1.empty() && !v2.empty())
{
int a1 = v1.back();
int a2 = v2.back();
if ( a1 == a2)
anc = a1;

v1.pop_back();
v2.pop_back();
}

return true;

}
else
return false;
}

[JMJAtlanta]

Just by quickly looking at the code (I did not compile or anything), the function FindComonAncestor looks through a hierarchical tree and finds the common ancestor of two "nodes" which are integers.

Does that answer your question?

[jasleen90]

It does search common ancester but I want to understand the program, step by step, if you can please

[Edward Donahue]

i know this is simple, i keep searching but dont know what key words to use. please help

[JMJAtlanta]

Okay, I reformatted the code so we can talk about it. Here it is:

#include <vector>

struct node
{
	node(int i, node * l =NULL, node * r=NULL): id(i), left(l), right(r) {}; /*wats dis ":",meaning*/
	int id;
	node * left;
	node * right;
};

bool FindNode(node * root, int id, std::vector& vec)// again can't get it
{
	if (root == NULL)
		return false;
	else if(root->id == id)
	{
		vec.push_back(id); //???
		return true;
	}
	else if ( FindNode( root->left, id, vec)) //???
	{
		vec.push_back(root->id);//??
		return true;
	}
	else if ( FindNode(root->right, id, vec))
	{
		vec.push_back(root->id);
		return true;
	}
	else
		return false;
}

// Please explain this code in simple terms
bool FindCommonAncestor( node * root, int n1, int n2, int & anc)
{
	std::vector v1, v2;
	if (FindNode(root, n1, v1) && FindNode(root, n2, v2))
	{
		//has common;
		int anc;
		while (!v1.empty() && !v2.empty())
		{
			int a1 = v1.back();
			int a2 = v2.back();
			if ( a1 == a2)
				anc = a1;

			v1.pop_back();
			v2.pop_back();
		}
		return true;
	}
	else
		return false;
}

The first question I see is on line 5. The colon is part of the constructor. It is a shortcut way of assigning values to the node object's variables. Line 5 could be rewritten as:

	node(int i, node* l = NULL, node* r = NULL) {
		id = i;
		left = l;
		right = r;
	};

which would do the same thing, but with more typing. Are you with me so far?

[jasleen90]

Thank you so much for reformatting, its much more readable now.
Yes I got it till here.

[JMJAtlanta]

The basis of this chunk of code is what is called a doubly linked list. Think of it as a line. Each item on the line knows itself, what is to the left, and what is to the right. Remember that the items on each end of the line may have nothing to the left or right.

So your next question was on line 11. This function is called FindNode, and is used to find a particular place on that line. In order to do so, it needs 3 pieces of information.

1) The beginning of the line (called "root" here).
2) The item being looked for (called "id" here).
3) A place to store the result (called "vec" here).

If it finds the item, the function returns "true". If not, it returns "false." That is why the line begins with the word "bool," which tells us what the function comes back with.

Do you think you've got line 11 understood now?

[jasleen90]

Yes quite a bit.

But can you elaborate a little on

std::vector& vec

in the 11th line about vector class and std.
Why did we use these here or why to write in this way?

[JMJAtlanta]

A vector is a collection, and is in the "standard" library. In your code you can refer to it in a few ways.

Option 1:

#include <vector> // include the necessary header file

std::vector v; // declare a variable called "v" that is a vector, use the one defined in the std namespace 

or Option 2:

#include <vector> // include the necessary header file

using namespace std; // now we can use anything in the std library as if it were defined in our current namespace

vector v; // declare a variable called "v" that is a vector, it is somewhat ambiguous as to where vector is defined. 

So, that is why you see "std::" before vector. It says "use the vector that is part of the "std" namespace instead of from any other namespace.

Personally, I liked option 1 when I started, as it helped to get me familiar with where classes came from. Option 2 makes coding quicker, with perhaps a tad less information.

Now, about the ampersand. That tells the compiler to not make a copy of the vector for use in the function. Instead, use the actual vector. That means that if the vector is modified, when the function ends, the function that called it can look inside the vector and see the changes.

Without the ampersand, the vector is copied. Any changes are made to the copy of the vector, not the original vector.

For more information on this, look up "pass by reference", or look at this article:

http://www.cplusplus.com/doc/tutorial/functions2/

[jasleen90]

Thanks a lot. I really got it till here. You explain really well.

[JMJAtlanta]

So now we move on to the guts of the FindNode function.

What the FindNode function does, is look to see if the number you passed in (the "id" variable) matches the position on the line you also passed in (the "root" variable).

If it does, add the "id" to the collection. That is done on line 17. Then return to the calling function (line 18).

If the id you passed in doesn't match the current position, call the FindNode function, looking to the left of the current position. That is done on line 20. If we find it there, put the current position into the collection, and return to the calling function (lines 22 & 23).

If by now, it still hasn't found it, look to the right of the current position. That is done on line 25. If we find it, put the current position into the collection, and return to the calling function (lines 27 & 28).

If we get to line 30, that means that the id we passed in is nowhere to be found on the current line, and we return to the calling function with "false".

Because this function calls itself (lines 20 and 25), it makes it difficult to think about what is really going on. This is called a "recursive function" and can be confusing. So step through the method in your head, and try to visualize the line, and looking at positions on the line, one at a time, looking for a match.

If it is still fuzzy, google "recursive function" and see if another explanation makes the concept clear.

When you have all that down, you're ready to tackle the complexities of the next method. You're almost there!

Let me know if you need clarification on any of the above.

[jasleen90]

Yes I got it . This is good when you can understand it.

[JMJAtlanta]

So with that knowledge, have you deciphered what is going on in the FindCommonAncestor method?

[jasleen90]

Yes quite a lot but where are the functions push_back and pop_back defined ?

[JMJAtlanta]

Here:

http://cplusplus.com/reference/stl/vector/

[jasleen90]

OK Finally I got it.
Thank you thanks a lot really.
I never thought I 'll be able to understand.