Binary Search Tree Crashes

Question

I am implementing a Binary Search tree in C++ I have the following code to add an entry to the tree:

void tree::add(int n)
{
    int found;
    leaf *t,*parent;
    findparent(n,found,parent);
    if(found==YES)
        cout<<"\nSuch a Node Exists";
    else
    {
        t=new leaf;
        t->data=n;
        t->l=NULL;
        t->r=NULL;

        if(parent==NULL)
            p=t;
        else
            parent->data > n ? parent->l=t : parent->r=t;
    }
}

In my main, I am using a map to store the values read from a text file as integer. Now, when I pass the value to the add function it crashes the program.

int main()
{
    tree t;
    map<int,int> word;
    map<int,int>::iterator count;
    string str;
    int num;
    string space ="";
    while((str=value(cin))!=space )
    {
        num = atoi(str.c_str());
        ++word[num];
    }
    int size = (int) word.size();
    int data[size];
    int x = 0;
    for(count = word.begin(); count!=word.end(); ++count){
        data[x] = (*count).first;
        x = x+1;
    }
    for (int iter = 0; iter<size; iter++){
        int x = 3 * data[iter];
        t.add(x);
    }

    return 0;
}

What I am doing here is, I convert the user input to integers using atoi and then add them to map. Then I get the size of the map and use that to fill an array with the elements. Now, when I iterate through the array and try to pass the array elements to the tree using add function, it is crashing the program. The program works fine, when I am trying to add a fixed array element. For eg:

int data[] = {6,7,8,9};

if I have this fixed array in my main and pass the elements to add, it works fine, this makes me feel there is no issue with add method. Please help me in finding the issue, am confused

Pastebin Link of entire program: http://pastebin.com/SWqTccJf

Answer 1

I think Tyler Hyndman is right that it's not standard C++. However, g++ for example does support this C99-ish "language extension". It doesn't take away from the fact that it's generally a bad practice to allocate arrays on the stack whose size is not known at compile-time, and could in fact be quite large.

My guess is that there's a bug in code which has not been supplied. Some bugs that involve memory/pointer issues can be masked depending on the contents of memory, which can make them frustrating. Anyway I don't see a bug in the supplied code. I would pay attention to exactly where it crashes, and what is the program's state at the point of the crash.

For best help, provide the minimum (yet sufficient) code to reproduce the problem. Maybe use pastebin if it seems like too much?

//EDIT// OK I looked at your full code listing.

See this revised code. The main differences:

1) You have a bug in the code the clears out the tree. Tree::del() should not be invoked here, because it's for removing a particular value. It has to find the node to be removed, then deal with various special cases. When you're wiping out the contents of the tree, you can just go ahead and recursively delete all the nodes. Easy & quick!

2) I unified your two find functions into one.

3) There was a bug in Tree::del for the case where the node being removed is the root. When the root node is being removed, parent will be NULL...

4) The logic for reading numbers from the input is changed.

I hope you'll study the code & see what's changed & why. Also remember to see exactly where your code crashes & get as much information as you can about the crash instead of just saying "aw darn, it crashed!".

Best regards :)

Answer 2

In C++ you can not use

int data[size];

when size is not known at compile time. Either use

int * data = new int[size];

// use data

delete [] data; // remember to delete

Or, since this is C++, use a std::vector

std::vector<int> data(size);