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. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    32

    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. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,855
    > i don't know why mine doesn't work...
    You're missing return statements (which your friend has).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    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. #4
    Registered User
    Join Date
    Feb 2010
    Posts
    32
    Quote Originally Posted by bernt View Post
    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!!

  5. #5
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    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. #6
    Registered User
    Join Date
    Feb 2010
    Posts
    32
    Quote Originally Posted by bernt View Post
    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. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    28
    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. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,855
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Registered User
    Join Date
    Feb 2010
    Posts
    32
    Quote Originally Posted by Feengur View Post
    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?

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Feb 2010
    Posts
    32
    Quote Originally Posted by iMalc View Post
    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...?

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by winggx View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fscanf()
    By Maz in forum C Programming
    Replies: 15
    Last Post: 08-31-2009, 09:30 AM
  2. find() command
    By kiros88 in forum C Programming
    Replies: 2
    Last Post: 08-06-2009, 05:37 PM
  3. count/display non-repeated element of array
    By azsquall in forum C++ Programming
    Replies: 15
    Last Post: 07-10-2008, 10:42 AM
  4. Find the second HWND of two identical elements
    By guitarist809 in forum Windows Programming
    Replies: 1
    Last Post: 07-02-2008, 02:31 AM
  5. Replies: 4
    Last Post: 01-05-2008, 11:30 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21