Binary tree traversal causes stack overflow

Question

So I'm making a binary search tree implemented through arrays (if parent's index is i, then left child's index is (i * 2 + 1), and right child's index is (i * 2 + 2).

Whenever I'm trying to traverse the tree (pre-orderly), I'm getting a stack overflow during the 3rd pre-order function call.

Here's my code for pre-order function:

void traversePreOrder(Tree tree, int index)
{
    printf("%d\n", index); //debug
    if (tree.data[index].accNumber != 0) //all .accNumber values are initialized as 0
                                   // at the start of the program to mark empty nodes.
    {
        printf("printing: %d\n", index); //debug
        printNode(tree.data[index]);

        if (tree.data[index * 2 + 1].accNumber != 0)
        {
            printf("will print: %d\n", index * 2 + 1); //debug
            traversePreOrder(tree, index * 2 + 1);
        }

        if (tree.data[index * 2 + 2].accNumber != 0)
        {
            printf("will print: %d\n", index * 2 + 2); //debug
            traversePreOrder(tree, index * 2 + 2);
        }
    }
    else
        return;
}

Here is the output of pre-order traversal:

0
printing: 0
User: Dumbledore
Account number: 53167
Account type: public
Account balance: 4597.54
Is account in debt? Yes

will print: 1
1
printing: 1
User: Stark
Account number: 13497
Account type: private
Account balance: 1549.50
Is account in debt? No

will print: 3

Process returned  255 (0xFF)   execution time : 5.856 s
Press any key to continue.

The tree is supposed to look like:

(only accNumber values)
                    53167
                  /       \
              13457      74310
                 \       /   \
               43158  71401  79473
                /      /       \
             14741   69690    99751

Thank you for your help.

Update

Changing maximum tree capacity from 1000 to 50 somehow solved the problem. If somebody could explain why, that would be nice.

I have a strong suspicion that you are reading beyond initialized data within your array and therefore recursing forever. As a quick test, can you make sure that your whole tree.data[] structure is cleared to 0 (so that a read into data not yet written returns a 0 and fails gracefully) so that this can be ruled out? — Michael Dorgan
– Michael Dorgan, Commented May 13, 2015 at 17:48
Right after I create the tree I use this function: void initializeTree(Tree * tree) { if (tree == NULL) return; for (int i = 0; i < MAX_TREE_CAPACITY; i++) { tree->data[i].accNumber = 0; } } — Haris Vitunskas
– Haris Vitunskas, Commented May 13, 2015 at 17:50
You cannot probe data unless the index used is known to be within the limits of data's magnitude. Just because you have a node in your array doesn't mean both its kids are there as well. Ex: your posted tree is storable in an array of 16 nodes, Ask yourself what your code does when you recurse to examine the children of index 15. Checking tree.data[index * 2 + 1].accNumber != 0 isn't enough. Before that you need to know that index * 2 + 1 is within 0..(n-1), where n is the magnitude of data in the first place. — WhozCraig
– WhozCraig, Commented May 13, 2015 at 17:51
@WhozCraig Maximum capacity of the tree is 1000 nodes, so in this case it shouldn't be a problem (or am I not interpreting your comment right?). Thank you for the tip though, I'll add that to the code. — Haris Vitunskas
– Haris Vitunskas, Commented May 13, 2015 at 17:59
There is is absolutly no information in your question about the absolut tree capacity. How do you expect anyone to explain? — Gabor Angyal
– Gabor Angyal, Commented May 13, 2015 at 19:25

Gabor Angyal · Accepted Answer · 2015-05-13 18:20:56Z

You state that:

all .accNumber values are initialized as 0 at the start of the program to mark empty nodes.

This is not a strong enough criterion for the recursion to stop.

If you want to be explicit you should make an upperbound to the index and make sure you don't exceed it. For example: if tree.size iz the number of nodes in the tree, you should also chack before each step of the recursion, like this:

    int left_child_idx = index * 2 + 1;
    if (tree.data[left_child_idx].accNumber != 0 && left_child_idx < tree.size)
    {
        printf("will print: %d\n", index * 2 + 1); //debug
        traversePreOrder(tree, index * 2 + 1);
    }

Or, if you do not want to do this, you should make sure, that there is two terminating leaf with 0 accNumber for all your last nodes.

In this datastructure that actually means that the second half of your data array should solely consist of such terminating leafs.

Looks ugly, but I hope you see it:

                      53167
                  /           \
              13457             74310
             /   \            /       \
            0      43158     71401     79473
          /  \     /   \     /    \      /  \
         0    0   14741  0  69690  0    0   99751
        /\    /\   /\    /\   /\   /\   /\   /\
       0  0  0  0 0  0  0  0 0  0 0  0 0  0 0  0

And as an array:

[53167, 13457, 74310, 0, 43158, 71401, 79473, 0, 0, 14741, 0, 69690, 0, 0, 99751,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

There is 31 element, 99751 is the 15th. Would any of the second half be non-zero, you would get an overflow.

Collectives™ on Stack Overflow

Binary tree traversal causes stack overflow

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related