Find a value in a binary tree avoiding stackoverflow exception

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 Node {

    // keep these​​​​​​​​‌‌‌‌‌​​‌‌​​​​​​‌​‌​‌‌‌​ fields
    Node left, right;
    int value;

    public Node 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.

Jon Skeet
people
quotationmark

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 Node find(int v) {
    Node 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 Node find(int v) {
    Node 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;
}

people

See more on this question at Stackoverflow