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.

What does `.getData()` do? You're probably in either a very deep loop or an infinite one somewhere. — OMGtechy, Mar 17 '14 at 13:01
the .getData() is simply a getter method for the data attribute which is a String. I don't know... Is weird that if I am going with the debugger, the exception is thrown at the first line, so doesn't reach the recursive calls. — Bogdan Niculeasa, Mar 17 '14 at 13:06
What happens when you set a breakpoint in the .getData() function? — David, Mar 17 '14 at 13:09
It seems to me that your second if statement `if (((String) node.getData()).equalsIgnoreCase(symbol))` is exactly the same as the first `if (node.getData().equalsIgnoreCase(symbol))`. You're using `node.getData()` in both cases, and since that already returns a String, casting it again to a String in the second if-statement is not going to make a difference. — Erwin Bolwidt, Mar 17 '14 at 13:09
As @OMGtechy hinted at, the recursion is in the `getData` method and not in the `getNodeValue` method so you posted the wrong method here. — Erwin Bolwidt, Mar 17 '14 at 13:11
I have updated the code and removed the duplicate call as Erwin Bolwidt said. But the exception still occurs. No, I have not posted the wrong method, the node.getData() method is simply a getter as I said before, namely: public String getData() { return this.getData(); } — Bogdan Niculeasa, Mar 17 '14 at 13:20

score 1 · Accepted Answer · answered Mar 17 '14 at 13:18

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

@Costy The stack overflow is coming from this.getData(); in your getData function. It is basically calling itself instead of returning any data. The above code only works because you don't call getData anymore, but please remove that function as it will produce the same stackOverflow the next time you call it. — David, Mar 17 '14 at 14:43
@David My last code section is only a replacement for the third and the fourth if statement, not for the entire method (the code in the OP was changed after I posted my answer, I'm not sure why it is now calling `node.getLeftChild().getLeftChild()` rather than just `node.getLeftChild()`) — Erwin Bolwidt, Mar 17 '14 at 14:46
@ErwinBolwidt Your suggestions are good. He also posted his GetData function which is the problem as all it does is call itself. — David, Mar 17 '14 at 14:53
Yes, you wew both right, sorry for being so stupid... Thank you all for your answers and for you time wasted with me. I really appreciate. — Bogdan Niculeasa, Mar 18 '14 at 22:03

score 0 · Answer 2 · edited May 23 '17 at 12:11

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.

Stackoverflow error when recursively searching in a tree

2 Answers2