CODEWITHSUNDEEP
javarecursionbinary-search-tree
Eyzuky
Eyzuky

Reputation: 1945

StackOverflowError while traversing a binary search tree in Java

I have a method that returns the deepest node in a BST. I have this code which raises a StackOverflow error:

public int getDeepestNode(AvlNode head) {
    if (head == null) {
        return 0;
    } else {
        return (Math.max(getDeepestNode(head.getLeftNode()), getDeepestNode(head.getRightNode())) + 1);
    }
}

To me it looks fine, why is it raising the error?

Upvotes: 0

Views: 502

Answers (1)

Joop Eggen
Joop Eggen

Reputation: 109597

getDeepestNode must occur repeatedly on the stack.

More than likely you have a cycle in the AVL tree. The naming, head, already might be an indication of unclean thoughts. Debugging helps. Alternatively, you might harden your code as:

public int getDeepestNode(AvlNode head) {
    return getDeepestNodeSafe(head, new ArrayList<AvlNode>());
}

public int getDeepestNodeSafe(AvlNode head, List<AvlNode> pathFromRoot) {
    if (head == null) {
        return 0;
    } else {
        if (pathFromRoot.contains(head)) {
            StringBuilder sb = new StringBuilder("Cycle: ");
            for (AvlNode node : pathFromRoot) {
                if (node == head) {
                   sb.append("***");
                }
                sb.append(node).append("; ");
            }
            Logger.getLogger(getClass().getName()).log(Level.WARN, sb.toString());
            return 0;
        }
        pathFromRoot.add(head);
        int depth = Math.max(getDeepestNodeSafe(head.left, pathFromRoot),
                             getDeepestNodeSafe(head.right), pathFromRoot) + 1;
        pathFromRoot.remove(pathFromRoot.size() - 1); // Undo
        return depth;
    }
}

Throwing an IllegalStateException would definitely be better, but with this code you might find the error faster (or not).

Upvotes: 2

Related Questions