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

This is a discussion on to find if the given element is in the BST or not... within the C Programming forums, part of the General Programming Boards category; this is my code Code: int memberbst (int i, struct node *t) { if (i > t->data) { memberbst (i, ...

1. ## 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...

2. > i don't know why mine doesn't work...
You're missing return statements (which your friend has).

3. 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!

4. 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...
thx!!

5. 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.

6. 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)

7. 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

8. Try this (your) code with an extra line added.
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;
}
printf( "Oops - I wonder what garbage we're going to return now?\n" );
}```
If you see that, you're falling off the end of the function WITHOUT a return statement.
So what you get instead is any old rubbish.

9. Originally Posted by Feengur

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?

10. 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.

11. 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.
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...?

12. Originally Posted by winggx
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...?
Yes that's correct.
Yes you could use just an 'if' instead of an 'else if' for this. In general that can make it slightly less efficient, but in this case you're performing a return from inside each of your 'if' or 'else if' cases anyway so it wont evaluate any other conditions after going into one case, and will probably generate the exact same machine code with or without the 'else's.