1

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;
}
TheEagle
  • 117
  • 2
  • 8

3 Answers3

2

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
Mike Elofson
  • 2,017
  • 1
  • 10
  • 16
  • Thanks. But I still don't understand how it can pass the `if(value == node.getValue())`-test and not returning true? – TheEagle Jun 30 '14 at 20:08
  • 1
    @TheEagle you understand how recursion works, more or less? You called `contains` from somewhere (main, or whatever), and `contains` calls itself, and then that `contains` calls itself, until one of them finds the value. `main->contains->contains->contains`. The final `contains` returns `true`, but it doesn't return directly to `main`, it returns to the `contains` that called it, from the point that it was called. And then execution continues from that point. And the next `return` that is executed is `return false`. – Blorgbeard Jun 30 '14 at 20:16
  • Blog beat me to the response. I've updated my answer and it shows how you can access the return calls and return the value without having an instance variable. You should not use an instance variable in this problem. I don't have the node class to test it, but that should work. – Mike Elofson Jun 30 '14 at 20:22
  • Just wrote up a quick Node class to test it with. The code solution I posted I can verify is working as intended. – Mike Elofson Jun 30 '14 at 20:31
  • Test your class with `250` instead of `7`. – PM 77-1 Jun 30 '14 at 20:34
2

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.

Steve Harrington
  • 942
  • 1
  • 7
  • 18
  • 1
    This is actually an interesting situation due to the existence of `integer cache`. For example, see [When comparing two Integers in Java does auto-unboxing occur?](http://stackoverflow.com/questions/1514910/when-comparing-two-integers-in-java-does-auto-unboxing-occur). So the result will vary depending whether integer value is below 128 or not. – PM 77-1 Jun 30 '14 at 20:31
  • That's an interesting link. It sounds like from a compiler point of view there is a difference between initializing an Integer via autoboxing (e.g. Integer x = 10;) and explicit construction (e.g. Integer x = new Integer(10); etc.) - would not have expected that. Thanks. – Steve Harrington Jun 30 '14 at 20:37
1

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;
}
Eran
  • 387,369
  • 54
  • 702
  • 768
  • 1
    You can return the value in the first if statement. Imagine a situation where it is a binary tree, and is created by adding 5, 3, 7. If you use your method and call .contains(root,7), it would return false because 7 is not on the left side, it is on the right side. But you are returning whatever you get as a result from the left side only. – Mike Elofson Jun 30 '14 at 20:34
  • @MikeElofson I noticed this error. Your solution with the local variable worked. Thanks. – TheEagle Jun 30 '14 at 20:54