segfault after return 0;

Question

I wrote a program to test my binary tree and when I run it, the program seems to crash (btree.exe has stopped working, Windows is checking for a solution ...).

When I ran it through my debugger and placed the breakpoint on the function I suspect is causing it, destroy_tree(), it seemed to run as expected and returned back to the main function. Main, in turn, returned from the program but then the cursor jumped back to destroy_tree() and looped recusively within itself.

The minimal code sample is below so it can be ran instantly. My compiler is MinGW and my debugger is gdb (I'm using Code::Blocks).

#include <iostream>

using namespace std;

struct node
{
    int key_value;
    node *left;
    node *right;
};

class Btree
{
public:
    Btree();
    ~Btree();
    void insert(int key);
    void destroy_tree();

private:
    node *root;

    void destroy_tree(node *leaf);
    void insert(int key, node *leaf);
};

Btree::Btree()
{
    root = NULL;
}

Btree::~Btree()
{
    destroy_tree();
}

void Btree::destroy_tree()
{
    destroy_tree(root);

    cout<<"tree destroyed\n"<<endl;
}

void Btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
  }
}

void Btree::insert(int key, node *leaf)
{
    if(key < leaf->key_value)
    {
        if(leaf->left!=NULL)
            insert(key, leaf->left);
        else
        {
            leaf->left = new node;

            leaf->left->key_value = key;
            leaf->left->left = NULL;
            leaf->left->right = NULL;
        }
    }
    else if (key >= leaf->key_value)
    {
        if(leaf->right!=NULL)
            insert(key, leaf->right);
        else
        {
            leaf->right = new node;

            leaf->right->key_value = key;
            leaf->right->left = NULL;
            leaf->right->right = NULL;
        }
    }
}

void Btree::insert(int key)
{
    if(root!=NULL)
    {
        insert(key, root);
    }
    else
    {
        root = new node;

        root->key_value = key;
        root->left = NULL;
        root->right = NULL;
    }
}

int main()
{
    Btree tree;
    int i;

    tree.insert(1);

    tree.destroy_tree();

    return 0;
}

As an aside, I'm planning to switch from Code::Blocks built-in debugger to DDD for debugging these problems. I heard DDD can display visually pointers to objects instead of just displaying the pointer's address. Do you think making the switch will help with solving these types of problems (data structure and algorithm problems)?

Answer 1

Your destroy_tree() is called twice, you call it once and then it gets called after the execution leaves main() from the destructor.

You may think it should work anyway, because you check whether leaf!=NULL, but delete does not set the pointer to NULL. So your root is not NULL when destroy_tree() is called for the second time,

Answer 2

Not directly related (or maybe it is) to your problem, but it's good practice to give structs a constructor. For example:

struct node
{
    int key_value;
    node *left;
    node *right;

    node( int val ) : key_val( val ), left(NULL), right(NULL) {}
};

If you do this, your code becomes simpler, because you don't need worry about setting the pointers when you create a node, and it is not possible to forget to initialise them.

Regarding DDD, it;'s a fine debugger, but frankly the secret of debugging is to write correct code in the first place, so you don't have to do it. C++ gives you a lot of help in this direction (like the use of constructors), but you have to understand and use the facilities it provides.

Answer 3

Btree::destroy_tree doesn't set 'root' to 0 after successfully nuking the tree. As a result, the destructor class destroy_tree() again and you're trying to destroy already destroyed objects.

That'll be undefined behaviour then :).

Answer 4

Once you destroy the root.
Make sure it is NULL so it does not try to do it again (from the destructor)

void Btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;

    leaf = NULL; // add this line
  }
}