Kingamere Kingamere - 6 months ago 36
Java Question

Java return boolean true using recursion

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?


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);