CODEWITHSUNDEEP
javarecursiondata-structuresreturnbinary-tree
sam_rox
sam_rox

Reputation: 747

how to use return keyword in a find operation in binary search tree

This is my method to find if a particular node is there in a binary tree.Here's my method and it works fine.

public boolean find(BinaryNode p,int x){
        if(p==null){
            return false ;
        }
        else{
            if(x==p.element){
                return true;

        }       
        else if(x<p.element){
            return find(p.left,x);
        }
        else {
            return find(p.right,x);
        }
    }


}

My question is if I don't insert return keyword inside else if(x<p.element){ and else { I get an error as missing return statement.
Say I have a binary tree consisting of elements 5,4,6,60,25,10 .
So if i am searching for 10 there's a time that 

if(x==p.element){
    return true;

is satisfied because of recursive calls.Then there's a return statement to be found.
If i am searching for an element that's not in tree eventually I would reach the statement

if(p==null){ return false ; },there we find a return statement.

Therefore even I don't have the return in else if and else clauses somehow there's a way that I finally reach a return statement right?So what's wrong with not having return keyword in else if and else clauses.
Why do I have to have it there?
Why can't I do it as

`public boolean find(BinaryNode p,int x){
        if(p==null){
            return false ;
        }
    else{
        if(x==p.element){
            return true;

        }       
        else if(x<p.element){
             find(p.left,x);
        }
        else {
             find(p.right,x);
        }
    }


}`

Upvotes: 1

Views: 178

Answers (3)

Pablo Francisco P&#233;rez Hidalgo
Pablo Francisco P&#233;rez Hidalgo

Reputation: 27702

The closest to the way you want your if-else if-else clause to behave is using the ? conditional expression:

public boolean find(BinaryNode p,int x)    
{    
        if(p==null) {    
                return false ;    
        }    
        else {    
         return (x==p.element)?true:(x<p.element?find(p.left,x):find(p.right,x));
        }
}

Other option is to store the value to be returned in a local variable and only return it at the end of your method: 

public boolean find(BinaryNode p,int x)
{
    boolean returnValue = false;
    if(p!=null)
    {
        if(x==p.element){
            returnValue = true;

        }       
        else if(x<p.element){
            returnValue = find(p.left,x);
        }
        else {
            returnValue = find(p.right,x);
        }
    }
    return returnValue;
}

And my favorite way, using short-circuit evaluation of logical expressions:

public boolean find(BinaryNode p,int x)
{
    if(p==null) return false;
    return x==p.element || (x<p.element && find(p.left,x)) || find(p.right,x);
}

Since Java's || and && operators won't evaluate their right part expression when the left part already determines their result. If x==p.element is true, then true will be returned without evaluation the rest of the line. If not, then (x<p.element && find(p.left,x)) will be evaluated following the same rule. Note how find(p.left,x) won't be evaluated when x<p.element is false.

Upvotes: 1

Braj
Braj

Reputation: 46861

Therefore even I don't have the return in else if and else clauses somehow there's a way that I finally reach a return statement right?

No compiler doesn't know about it. Compiler doesn't know what will be value of x and p at run-time.

Compiler simply checks for all the possibilities of the return statement and there must be exit point of the method.

You need to provide the logic to move either in right direction or left direction of the binary tree.

The last two else-if are not responsible to actually return the result of the find method its used just to move in the right direction of the tree. Ultimately final result of the the find method will come out by first two if-else clause.

Upvotes: 0

JohnnyAW
JohnnyAW

Reputation: 2876

You need return statement because the find-function in the else if - else statement will return to the caller after its done, but the first-call function still have to return a value to the caller

Upvotes: 1

Related Questions