How can I prevent the stack overflow error?

Question

I am working on a Java project to involving quadtrees.
In this representation of the quadtree, the node with intensity -1 has 4 children and the node with any other intensity does not have children. I am given the preorder traversal of the quadtree and asked to convert it into the tree itself. The preorder traversal is provided to me in a file (each line containing one number). I keep getting into a stack overflow error because in my method I am using recursion and the file has 79,917 numbers.

This is the method I wrote. It works on smaller files/ But crashes on larger files.
In this method it receives an array containing the preorder traversal of the quadtree

public void createQT(Integer[] numbers){
    createQT(numbers, 1, root);
}

private void createQT(Integer[] numbers, int index, QTNode currentParent) {
    if (index >= numbers.length || numbers[index] == null) {
        return;
    }

    QTNode node = new QTNode();
    if (numbers[index] != -1) {
        node.setIntensity(numbers[index]);
        currentParent.addChild(node);
        createQT(numbers, index + 1, currentParent); 
    } else {
        currentParent.addChild(node);
        index++;
        for (int i = 0; i < 4; i++) {
            createQT(numbers, index, node); 
            index++;
        }
    }
}

seems to me like you're ending up with an endless loop, in which you keep creating new QTNode instances. — Stultuske
– Stultuske, Commented Apr 18, 2024 at 6:42
Please add an example call with concrete instance of numbers. How do you initialise root? — trincot
– trincot, Commented Apr 18, 2024 at 12:03

Maurice Perry · Accepted Answer · 2024-04-18 07:02:19Z

0

I believe that your problem is that you don't increment index correctly: An call to createQT may increment it by more than one if you find a node with four children. Try returning the index of the next node:

private int createQT(Integer[] numbers, int index, QTNode currentParent) {
    if (index >= numbers.length || numbers[index] == null) {
        return index;
    }

    QTNode node = new QTNode();
    if (numbers[index] != -1) {
        node.setIntensity(numbers[index]);
        currentParent.addChild(node);
        index = createQT(numbers, index + 1, currentParent); 
    } else {
        currentParent.addChild(node);
        for (int i = 0; i < 4; i++) {
            index++;
            index = createQT(numbers, index, node); 
        }
    }
    return index;
}

answered Apr 18, 2024 at 7:02

Maurice Perry

9,6802 gold badges15 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

trincot · Accepted Answer · 2024-04-18 13:02:22Z

There are a few issues:

root should be initialised in this process, because a new tree is built. So any trace of a potential previous tree should be cleared.
As the root has either no children or four children, the call made with index equal to 1 will go wrong: it assumes the root node was already created, and then creates again just one node, which becomes the child of that root. This violates the principle that a node has 0 or 4 children, and so the structure will be wrong from that point onwards.

Instead, you can better set the root to null and make a first call of the recursive function with index 0. Then in that execution check whether the very first node is created, and if so, assign it to root.
When a leaf-condition is encountered (i.e. numbers[index] != -1) your code makes a recursive call. But that is wrong. It passes node for currentParent, while we know it is a leaf, so it shouldn't become the parent of any node. We can also it is wrong by realising that this leaf may have siblings at its right, which still need to be processed, but yet there is no code that would link those future nodes to currentParent. By consequence nodes will be linked in the wrong way.

The depth of recursion should better match the depth of the tree that is being created. When having created a leaf, we should backtrack out of the recursion tree, by just returning.
The loop for creating the children does not correctly update index. 1 is added to it, but the number of nodes created by the recursive call will often be more than 1. This means that numbers[index] will be used multiple times, not only leading to a wrong tree construction, but also this repetition can grow exponentially for larger inputs. Together with the previous point where the recursive calls are made where they shouldn't, this can quickly consume the available stack space.

To get index updated correctly, have the recursive call return that updated index.

Suggested code:

    public void createQT(Integer[] numbers) {
        root = null; // start from scratch
        createQT(numbers, 0, null); // Use index 0 here
    }

    private int createQT(Integer[] numbers, int index, QTNode currentParent) {
        if (index >= numbers.length || numbers[index] == null) {
            return index;
        }

        QTNode node = new QTNode();
        // Allow for initialising the root
        if (currentParent == null) {
            root = node;  // First created node is the root
        } else {
            currentParent.addChild(node);
        }
        // Increment index if and only when node was created
        int intensity = numbers[index++];
        if (intensity != -1) { // Leaf
            node.setIntensity(intensity);
            // Don't make a recursive call here; just allow to go one level back
        } else { // Internal node with 4 children
            for (int i = 0; i < 4; i++) {
                index = createQT(numbers, index, node);
            }
        }
        // Return updated index, so the caller can continue there
        return index;
    }

Collectives™ on Stack Overflow

How can I prevent the stack overflow error?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related