Find value in binary tree avoiding stackoverflow exception

Question

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

I made an algorithm that works well when the value is not at a very deep level of the tree, but when the value is in a deep position, I get 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 anyone suggest me a solution to this problem (I heard of something like tail optimization recursion), but I'm not sure if it works in Java.

Answer 1

- while, " node, ".

:

• node ,
• node , , " node"
• , , null

- :

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 no appropriate subnode
        current = v < current.value ? current.left : current.right;
    }
    return null;
}

, , , :

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;
}

Answer 2

:

class Node {

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

    public Node find(int v){
        Node n = this;

        while (n != null)
        {
            if (v > n.value)
                n = n.right;
            else if (v < n.value)
                n = n.left;
            else // v == n.value
                return n;
        }

        return null;
    }
}

: , , . , node, , . , , ( ), ( ) ( ). , (while ), , , , , null.

: , if . if/else if/else.

Answer 3

, .

- node . , node , . , .

-, , , , - .

, , , . , .

Answer 4

Xss JVM, , . .

- Xsssize

( ). k K, KB, m M, MB, g G, GB. .

1024 :

-Xss1m

-Xss1024k

-Xss1048576

: https://docs.oracle.com/javase/8/docs/technotes/tools/windows/java.html

, , ( ) , .

Note: There is no need for a stack for the search operation, as John Skeet mentioned. The search does not need to track where it was. However, reverse tracking will require a reference to the parent, and we will need to make sure that we always start with the left child.