CODEWITHSUNDEEP
javabinary-search-tree
denis
denis

Reputation: 1

Recursively Search on a Binary Tree

can anybody help me to trace this piece of code if its correct or incorrect.i am studying recursion these days.

boolean search(Element element) {
    Element c=first;
    if(c==null)
        return false;
    else if(element.asset < c.asset)
        if(c.left==null)
            return false;
        else
            return search(c.left);
    else if(element.data>c.data)
        if(c.right==null)
            return false;
        else
            return search(c.right);
     else  
         return element.asset==c.asset;
}

Upvotes: 0

Views: 1691

Answers (3)

Jeff Grigg
Jeff Grigg

Reputation: 1014

It is syntactically correct Java. But I don't see how it could possibly be doing what you intend.

It appears that the 'element' parameter is the thing you are searching for and the 'first' field in the current class is the root of the binary tree.

It's unclear if the key for the binary tree and search (in the Element class) is 'asset' or 'data'. The 'less than' test uses 'asset', while the 'greater than' test uses 'data'. It seems likely that both lines should use the same field. It might be that one of these two fields ('asset' or 'data') should not be referenced in this method at all. Maybe the last line of the method should be just 'return true;'?

(I suspect that the "stop condition" and the "code isn't symmetric" answers above are both incorrect. But I could be wrong: It's hard to tell with only the code given.)

I agree that infinite looping is likely: I suspect that you need to create a second 'search' function that accepts two 'Element' parameters -- one being the thing to search for (like the current 'element' parameter) and the other being the next Element to search -- the equivalent of current local variable 'c'. I would do the "Extract Method" refactoring on everything in the body of the current 'search' method except the first line, and then change the two recursive calls to use the new method.

(Some of this is speculative, based on me guessing what you want or intend, given limited information. So I could, of course, be quite wrong.)

Upvotes: 0

Atreys
Atreys

Reputation: 3761

Your code isn't symmetric.

for one side, you call isExist(t.left), for another you call isExist(a.right)

You probably want to call t.left.isExist(a) and t.right.isExist(a), but that is purely speculative as you do not have a complete SSCCE for us to look at.

Upvotes: 1

amit
amit

Reputation: 178511

it lacks stop condition. you should check if t.left == null, or you will get NullPointerException. also, you should return t.left.isExist(..) OR t.right.isExist(...) and not isExist [you will want to invoke this method on the son]

currently, this version will get into infinite loop - because you will always check in the same root node.

Upvotes: 3

Related Questions