java- BST recursive find a value

Question

I have a BST tree. I want to create a method that gets a value and returns the level of the node containing it's value (root = 0), no such node? return -1. I would like to do it recursivly. this code works just fine:

    private int recursiveContains(BinaryNode node, int searchVal){
    int nodeKey = node.nodeKey;
    if (searchVal < nodeKey){
        if (node.leftChild != EMPTY_NODE)
            return 1 + recursiveContains(node.leftChild, searchVal);
    }else if (searchVal > nodeKey){
        if (node.rightChild != EMPTY_NODE)
            return 1 + recursiveContains(node.rightChild, searchVal);
    }
    return 0;
}

BUT, only as long as the tree contains the search value.

How do stop the iteration and return -1 when I reach a leaf and didnt find the value? Is it possible recursivle?

Thanks

Answer 1

You just need to adjust your final case. Right now, if the value isn't in the tree, you just return the depth of the node under which the value would be inserted, because your final case is just return 0. Instead, you need to explicitly check whether the current node is indeed the correct node. If it is, you can return 0; otherwise you should return -1. The recursive calls then need to look for that special value and handle it appropriately.

I'd probably put this explicit check--the base case of this being the requested node--at the beginning. Then at the end, your "fall-through" value (what you return if none of the other conditions are true) is -1. So you'll end up with something like this:

// WARNING: UNTESTED CODE
if (searchVal == nodeKey) {
    return 0;
} else if (searchVal < nodeKey && node.leftChild != EMPTY_NODE) {
    int childResult = recursiveContains(node.leftChild, searchVal);
    if (childResult != -1) { // Only use the child result if the value was found.
        return 1 + childResult;
    }
} else if (searchVal > nodeKey && node.rightChild != EMPTY_NODE) {
    int childResult = recursiveContains(node.rightChild, searchVal);
    if (childResult != -1) { // Only use the child result if the value was found.
        return 1 + childResult;
    }
}
// If you haven't returned by now, the value can't be found along this path.
return -1;