Java return boolean true using recursion

Question

I am trying to see if a value is contained in my Binary Search Tree, and I am traversing the tree using recursion. The problem is the function returns false as the last value on the call stack instead of true.

Here is pseudo code:

public boolean containsValue(Node node, Value v) {

   if (node.value.equals(v)) {
     return true;
   } 
   containsValue(node.left, v); // <- search left tree
   containsValue(node.right, v); // <- search right tree

   return false;
}

This always returns false.

However I can't do this because the second return statement is dead code:

 return containsValue(node.left, v);
 return containsValue(node.left, v);

So how would I fix this?

Answer 1

This solves the immediate problem, but is not the correct or efficient way to search a binary tree as it makes no decision about looking left or right, it just dumbly looks left and then right. Correct answer for that is here.

---

You want to return true if the left node contains it or (||) the right node contains it.

return containsValue(node.left, v) || containsValue(node.right, v);

And note that it will short circuit and not look in the right if the left contains it.

You can even make the whole thing:

return node.value.equals(v) ||
       containsValue(node.left, v) ||
       containsValue(node.right, v);