CODEWITHSUNDEEP
javabinary-tree
TheEagle
TheEagle

Reputation: 117

contains-method in binary tree always return false java

Can someone explain why this method always return false? Even though the statement if(value == node.getValue()) is true the method returns false. Something to do with recursion? I solved it by using a booelan-variable instead but I'm still curious why this doesn't work. Thanks.

public boolean contains(Node node, Integer value) {

    if(node != null && node.hasValue()) 
        if(value == node.getValue()) 
            return true;

    if(node.hasLeft())
        contains(node.getLeft(), value);
    if(node.hasRight())
        contains(node.getRight(), value);

    return false;
}

My solution(bool is an instance-variable):

public boolean contains2(Node node, Integer value) {

    if(node != null && node.hasValue()) 
        if(value == node.getValue()) 
            bool = true;

    if(node.hasLeft())
        contains2(node.getLeft(), value);
    if(node.hasRight())
        contains2(node.getRight(), value);

    return bool;
}

Upvotes: 1

Views: 3896

Answers (3)

Eran
Eran

Reputation: 393781

The return value of the recursive calls gets lost if you do nothing with it. Try :

public boolean contains(Node node, Integer value) {

    if(node != null && node.hasValue()) 
        if(value == node.getValue()) 
            return true;
    boolean found = false 
    if(node.hasLeft())
        found = contains(node.getLeft(), value);
    if(!found && node.hasRight())
        found = contains(node.getRight(), value);

    return found;
}

Upvotes: 1

Steve Harrington
Steve Harrington

Reputation: 942

In addition to the aforementioned issue with the return values...

As it stands, your logic looks like it will only work if you pass in the exact same Integer object (reference), for the parameter 'value' in your search, that you used when populating your tree. If you were to pass in another Integer object, even with the identical int value within it, your == test will fail. To work around that, use .equals method instead. Unless, of course, that's what you intended.

Upvotes: 2

Mike Elofson
Mike Elofson

Reputation: 2037

Your recursive calls

contains(node.getLeft(), value);

Are returning the value to you, but you never do anything with this value. Instead you ignore it, and after all of the nodes have been traversed you return false no matter what. You need to return the value of recursive calls here is how you can accomplish this with your code:

private boolean contains(Node node, Integer value) {
    if (node.getValue() == value) {
        return true;
    }

    boolean contains = false;
    if (node.hasLeft()) {
        contains = contains(node.getLeft(), value);
    }
    if (!contains && node.hasRight()) {
        contains = contains(node.getRight(), value);
    }

    return contains;
}

To test this I used:

public static void main(String[] args) throws Exception {

    Node top = new Node(5);
    top.setLeft(new Node(3));
    top.setRight(new Node(7));
    top.getLeft().setLeft(new Node(1));
    System.out.println("Contains 5? " + contains(top, 5));
    System.out.println("Contains 3? " + contains(top, 3));
    System.out.println("Contains 7? " + contains(top, 7));
    System.out.println("Contains 9? " + contains(top, 9));

}

Which gave me the output:

Contains 5? true
Contains 3? true
Contains 7? true
Contains 9? false

Upvotes: 2

Related Questions