Kingamere Kingamere - 4 months ago 20
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?

Answer

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