Searching in BST

[Sharan123]

I have done searching using first method the first one is using search with void and the second one using int return type.
The first method gives me correct output but with an excessive 2 statements "number not found" how do i remove number not found statement.
The second method gives me correct statement "number found" but a wrong value and like the previous case excessive two statements of "number not found" how do i make it correct by both methods

  //1 method
void search(Tree *temp,int elm)
{
	if(temp!=NULL)
	{
		if(temp->data==elm){
			cout<<"number found : ";
			cout<<temp->data<<endl;;
			return;
		}
		else if (elm>=temp->data)
			search(temp->Right,elm);
		else if (elm<temp->data)
			search(temp->left,elm);
	}
	cout<<"number not found\n";
}
//2 method
int search(Tree *temp,int elm)
{
	if(temp!=NULL)
	{
		if(temp->data==elm){
			cout<<"number found : ";
			return temp->data;
		}
		else if (elm>=temp->data)
			search(temp->Right,elm);
		else if (elm<temp->data)
			search(temp->left,elm);
	}
	cout<<"number not found\n";
}

[AbstractionAnon]

Both methods are recursive. Consider the recursive calls at lines 12/14 and 28/30. What happens when a recursive call is made and a match is found at a lower level? The recursive call returns and falls through to line 16 or 32 which tells you a match wasn't found.

[Sharan123]

Yes , but why does it have to print line 16 or 32 two times and another part of the question why does the 2nd method give a wrong return value?

[AbstractionAnon]

why does it have to print line 16 or 32 two times

How deep is your tree?

Lets say you have to recurse 5 levels down to find a match. On the 5th call to search, it finds the number and exits back to the 4th level. 4th level falls through to line 16/32 and prints "not found" even though you found a match. Now, the 4th level exits back to the 3rd level and falls through to 16/32, again printing "not found". etc, for the 2nd level and the 1st level.

Consider the following instead:

bool search (Tree *temp, int elm)
{   if (temp!=NULL)
    {   if (temp->data==elm)
            return true;  // number found
        if (elm >= temp->data)
            return search(temp->Right,elm);  // return result from lower level
        else 
            return  search(temp->left,elm);  // return result from lower level
    }
    return false; 
} 

why does the 2nd method give a wrong return value?

two problems:
1) What value gets returned if a match was found at a lower level via the calls at lines 28/30? The result of the recursive call is ignored.
2) What value ts returned if you fall through line 32?

[Sharan123]

What value ts returned if you fall through line 32?

Wait i think am getting confused in this return call , when i write return at line 25 it returns call back to function and return the up most value in the stack
which is a garbage value am i right but in c++ u can not go off parameters in the specified parameters??

[AbstractionAnon]

when i write return at line 25 it returns call back to function and return the up most value in the stack

I'm not sure i understand what you're saying there.

The return at line 25 exits only one level of recursion. It does not exit all the way back to the top. It exits to the previous call. Read through the example I gave you in my previous post. The 5th level call finds a value and returns it at line 25. Control resumes at line 28/30 of the 4th level. Note that the value found by the 5th level call is ignored by the 4th level.

which is a garbage value am i right but in c++ u can not go off parameters in the specified parameters??

Not sure what you're saying there either. There is no issue with parameters. For each nested call to search, the parameters are passed to the next level.