Stackoverflow error when recursively searching in a tree

Question

I am implementing the Shannon/Fano algorithm using Java and I am doing this by calculating the frequencies of symbols in a text file, and after that I put all these values in a tree. The problem is that when I am searching for a certain symbol in a tree I also have to update the code of the respective symbol (e.g If I go to left append 0, otherwise 1) and doing this recursively I am getting a stackoverflow error. Below is my code :

private String getNodeValue(Node node, String symbol) {
    if (node.getLeftChild() != null) {
        if (node.getLeftChild().getData().equalsIgnoreCase(symbol)) {
            node.updateCode(0);
            return node.getData() + "";
        }
    } else if (node.getRightChild() != null) {
        if (node.getRightChild().getData().equalsIgnoreCase(symbol)) {
            node.updateCode(1);
            return node.getData() + "";
        }
    }


    Node nextLeftNode = node.getLeftChild().getLeftChild();
    if (nextLeftNode != null) {
        getNodeValue(nextLeftNode, symbol);
    }

    Node nextRightNode = node.getRightChild().getRightChild();
    if (nextRightNode != null) {
        getNodeValue(nextRightNode, symbol);
    }

    // if symbol is not found return null
    return null;
}

and the stackoverflow error is triggered at the very first line of the method when the call to node.getData() takes place. This is my stack trace:

Exception in thread "main" java.lang.StackOverflowError
at ro.uvt.it.datastractures.Node.getData(Node.java:47)
at ro.uvt.it.datastractures.Node.getData(Node.java:47)
at ro.uvt.it.datastractures.Node.getData(Node.java:47)

And this is my getData() method:

public String getData() {
    return this.getData();
}

Any help or hint would be appreciated, Thank you.

Answer 1

There are many mistakes in your code.

As you showed in your stacktrace, the infinite recursion is in the getData method and not in the getNodeValue method, so you need to post the source code of the getData method.

But the getNodeValue method has many bugs as well.

Your first two if statements have exactly the same condition:

if (node.getData().equalsIgnoreCase(symbol)) {

and

else if (((String) node.getData()).equalsIgnoreCase(symbol)) {

the returns inside these if statements append an empty string to the result of getData(), which already returns String. Replace each of them with:

return node.getData();

are just a different way of writing the same, since getData() already returns a String so casting to String again doesn't make a difference.

Your next to if statements recursively call getNodeValue on leftChild and rightChild, but they never return anything, so you always end up returning null in your code once you're past the first two identical if statements in your method.

You code should probably read:

if (node.getLeftChild() != null) {
    String found = getNodeValue(node.getLeftChild(), symbol);
    if (found != null) {
        return found;
    }
}
if (node.getRightChild() != null) {
    String found = getNodeValue(node.getRightChild(), symbol);
    if (found != null) {
        return found;
    }
}

Answer 2

Almost certainly unbounded recursion. At a guess I'd say it was a mistake in the implementation of getLeftChild or getRightChild. I would suggest you step through in the debugger, and I'll bet you will quickly see where this goes.

However, if you have a very deep tree, you may discover that the stack overflow exception is legitimate, in which case you will need to revisit the algorithm. And the traditional technique of tail recursion appears to be hard to achieve in Java.