Evaluating if a stack overflow error is possible in a tree traversal recursive algorithm (Java)

Question

What is the best way to determine theoretically (i.e., without actually executing it) the circumstances in which a certain tree traversal recursive algorithm will produce a stack overflow in Java?

In order to clarify my question, consider the following example. Given a simple binary tree implemented in Java:

public class Node {
    private int value;
    private Node left;
    private Node right;
    ...

    //in-order traversal
    public void inOrder() {
        if (left != null) {
            left.inOrder();
        }
        System.out.println(value);
        if (right != null) {
            right.inOrder();
        }
    }
}

In this algorithm, the maximum number of nested recursive calls is linear with respect to the depth of the tree. So how can I estimate which is the maximum depth of the tree that will allow an in-order traversal algorithm (or similar) to complete without throwing a stack overflow error?

If the maximum stack size is assigned by thread by means of the -Xss option, is it correct to just divide this number to an estimation of each stack frame used by my recursive algorithm?

And is it correct to estimate the size of each stack frame by adding the size of parameters and local variables to the size of the program counter, where the program counter size depends on the architecture (32 bits vs 64 bits, etc...).

Am I missing something else?

UPDATE:

I do know that a recursive algorithm can be converted to an iterative one in order to avoid stack overflow errors. This is just a theoretical question regarding recursive algorithms.

Maybe a little off topic, but if you're nervous about getting a stack overflow here, why you just don't turn that into a loop and putting values into a processing array ? — JFPicard, May 03 '15 at 14:57
I agree with @JFPicard. Every recursive algorithm can be converted into an iterative one easily. — isnot2bad, May 03 '15 at 15:09
All algorithms which use methods calls can overflow the stack, the question is how deep the stack calls can get, and if that depends on the input. In case of recursive calls on a tree it depends on the tree depth. So typically a balanced tree can never be so deep to trigger this (but you can easily construct pathological cases). — eckes, May 03 '15 at 18:06

score 0 · Accepted Answer · answered May 03 '15 at 15:47

I understand that this is mostly theoretical question but it is valid question. You are right in your estimates. Except stack goes to Xms but local variables go to Xmx. So, based on real data what you use on each iteration and real size of available RAM depth of tree really varies.

Evaluating if a stack overflow error is possible in a tree traversal recursive algorithm (Java)

1 Answers1

Linked