Find a value in a binary tree avoiding stackoverflow exception

Question

I'm trying to find a value in a binary tree and returning the node that has the value I'm looking for.

I did an algorithm that works well when the value is not in a very deep level of the tree, but when the value is in a deep position I get a java.lang.StackOverflowError. Here is my code:

class Nope {
    
    Nope left, right;
    int value;

    public Nope find(int v){
        if(v > this.value && this.right != null)
            return right.find(v);
        if(v < this.value && this.left != null)
            return left.find(v);
        if(this.value == v)
            return this;
        return null;
    }
}

Can any one suggest me a solution about this issue (I heard about something like tail optimization recursion) but I'm not sure of it working in Java.

Answer 1

The simplest approach is to convert this into a while loop, which just maintains state of "the current node we're testing".

On each iteration of the loop, there are three possibilities:

• The current node has the right value, in which case you can return it
• The current node has a subnode on the correct "side", in which case you can continue iterating with that subnode as the new "current node"
• Neither of the above is the case, in which case the value isn't found and you can return null

So something like:

public Nope find(int v) {
    Nope current = this;
    while (current != null) {
        if (current.value == v) {
            return current;
        }
        // This will drop out of the loop naturally if there's no appropriate subnode
        current = v < current.value ? current.left : current.right;
    }
    return null;
}

Or with even less code, but perhaps less readably:

public Nope find(int v) {
    Nope current = this;
    // Keep navigating down the tree until either we've run
    // out of nodes to look at, or we've found the right value.
    while (current != null && current.value != v) {
        current = v < current.value ? current.left : current.right;
    }
    return current;
}