Thread: to find if the given element is in the BST or not...

this is my code

Code:

int memberbst (int i, struct node *t)
{
	if (i > t->data)
	{
		memberbst (i, t->right);
	}
	
	else if (i < t->data)
	{
		memberbst (i, t->left);
	}
	
	else if (i == t->data)
	{
		return 1;
	}
	
	else
	{
		return 0;
	}

}

and this one is another code from my friend

Code:

int memberbst (int i, struct node *t)
{
	if (i > t->data)
	{
		return memberbst (i, t->right);
	}
	
	else if (i < t->data)
	{
		return memberbst (i, t->left);
	}
	
	else if (i == t->data)
	{
		return 1;
	}
	
	else
	{
		return 0;
	}

}

what is the difference?
are both wrong? or one of them is correct...?
i don't know why mine doesn't work...

The difference is that your friend's function returns the value from the call to itself

Code:

Yours:
        if (i > t->data)
	{
		memberbst (i, t->right);
	}

Friend's:
        if (i > t->data)
	{
		return memberbst (i, t->right);
	}

Your friend's works recursively; yours will only work if the first test is significant (it will do the recursion but will not return a value from it...)

EDIT: Argh! Bested again! I need to learn to type faster!

Originally Posted by bernt

The difference is that your friend's function returns the value from the call to itself

Code:

Yours:
        if (i > t->data)
	{
		memberbst (i, t->right);
	}

Friend's:
        if (i > t->data)
	{
		return memberbst (i, t->right);
	}

Your friend's works recursively; yours will only work if the first test is significant (it will do the recursion but will not return a value from it...)

EDIT: Argh! Bested again! I need to learn to type faster!

I still don't quite get it...
I understand the return word makes the difference...but why?
I tried to trace my code, but I can't see what the problem is..
when int i is given, it has to be bigger or smaller than t->data
so it goes to either the first or second statement, and the first and second statement both recursivly call back the function...

and it will eventually hit the third or fourth statement....
i still cant see what is wrong...
need some advice
thx!!

i still cant see what is wrong...

You're correct, they both recursively call the function, but the difference is the retu... oh, I'm repeating myself.

Let's try an example:

Code:

1)You call the function
2)It tests: is (i > t->data)?
   3)Let's say yes.
4)It's called again, this time for (t->right)
5)is (i > t->data)?
   6)Let's say no.
7)is (i < t->data)?
   8)Let's say no.
9)is (i == t->data)?
   10)Let's say yes

11)Bingo! Return 1.
12)Control goes back to first call to memberbst.
13)No return statement! Returned value is lost. Function does not return any value.

I hope this clears things up.

Originally Posted by bernt

You're correct, they both recursively call the function, but the difference is the retu... oh, I'm repeating myself.

Let's try an example:

Code:

1)You call the function
2)It tests: is (i > t->data)?
   3)Let's say yes.
4)It's called again, this time for (t->right)
5)is (i > t->data)?
   6)Let's say no.
7)is (i < t->data)?
   8)Let's say no.
9)is (i == t->data)?
   10)Let's say yes

11)Bingo! Return 1.
12)Control goes back to first call to memberbst.
13)No return statement! Returned value is lost. Function does not return any value.

I hope this clears things up.

I don't understand 13...
what does it mean by go back to the first call?
isn't the function will end after it returns a value?

(**sorry, i am new to C, really appreciate your help)

Think about it like this....

Let's say you have a bag with 50 coins in it. 49 of those coins are copper, but 1 of them is pure gold.

You have been tasked with the job of finding that gold coin and returning it to your boss, so you pull out the first coin and it's just a copper coin. Being that you're lazy, you decide to pass this task on to a fellow coworker with the remaining 49 coins.

You tell him, "Bob, I need you to find the gold coin in this bag." He grabs the next coin and it happens to be the gold one.

For some reason Bob just walks off with the coin! And since he never RETURNed it to you, you cannot hand it off to your boss.

The mistake here is that you assume the return of the coin is implied, but you never told Bob to give it back.



Sorry if this was confusing. I know the 'real life' logic is off but this is programming and the computer only does what you tell it to do.

HTH,
-Feen

Originally Posted by Feengur

Think about it like this....

Let's say you have a bag with 50 coins in it. 49 of those coins are copper, but 1 of them is pure gold.

You have been tasked with the job of finding that gold coin and returning it to your boss, so you pull out the first coin and it's just a copper coin. Being that you're lazy, you decide to pass this task on to a fellow coworker with the remaining 49 coins.

You tell him, "Bob, I need you to find the gold coin in this bag." He grabs the next coin and it happens to be the gold one.

For some reason Bob just walks off with the coin! And since he never RETURNed it to you, you cannot hand it off to your boss.

The mistake here is that you assume the return of the coin is implied, but you never told Bob to give it back.



Sorry if this was confusing. I know the 'real life' logic is off but this is programming and the computer only does what you tell it to do.

HTH,
-Feen

Thanks, it makes more sense to me now.
But hum... even I add return to my first and second statement, is it true that my code is still wrong?

Because the code testing system of my school says it crash...but I can't figure out why...
can anyone spot any error from my code?

Originally Posted by iMalc

They're both wrong because they both crash if searching for a value that is not in the tree.

Think about what you're written, when can 'i' be not less than nor greater than nor equal to t->data? NEVER! So it can never reach the return 0 line! That's because that case is wrong. It should be checking for NULL at the start instead of checking for the impossible at the end.
Stop copying bad code from your friend huh

Thank you very much. I understand it now.
I have one more questinn though.

Is it ok if I just use if statement?
I am kind of confused the difference between if and else if...
this is my understanding between if and else if
if = the program will go through other if statements even if the program meets the first if statements.

else if=will only go through 1 if/else if statement

am i right...?