Kingamere - 1 year ago 72

Java 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 Source

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