Recursive Function Missing Return Statement

Question

I'm new to recursion and I don't see why this function won't compile. It is apparently missing a return statement. From testing it also seems as though my return statements do not return?

// recursive search method
public BinaryTree<T> recursiveSearch(BinaryTree<T> t, T key) {
    if (key.compareTo(t.getData()) < 0) {
        if (t.getLeft() != null) {
            recursiveSearch(t.getLeft(), key);
        } else {
            return null;
        }
    } else if (key.compareTo(t.getData()) > 0) {
        if (t.getRight() != null) {
            recursiveSearch(t.getRight(), key);
        } else {
            return null;
        }
    } else if (key.compareTo(t.getData()) == 0) { // key is found
        return t;
    } else { // not in binary tree
        return null;
    }
}

Answer 1

The problem is on the lines inside the if branches that make recursive calls.

Your code will behave correctly when it reaches any of your else branches, because all of them have return null. If code takes one of the if branches, however, the control would reach the end of your method without hitting a return. The fix is simple - add the missing returns:

return recursiveSearch(t.getRight(), key);