1

I've seen this question asked before here, specifically

Generic binary tree node destructor issue and Binary Search Tree Destructor among other things

but so far the answers I got was to set the Node pointers to NULL in the constructor. Here is the code of my constructors and destructors for the Node and the Tree.

template <class Type>
class Node {
protected:
    Type data;
public:
    Node<Type>(Type data) { this->data = data; }
};

The Binary Tree Node inherits from the Node above (I know that it would be easier to not use inheritance and simply go with a BinaryTreeNode straight with data, but I chose to do it this way because I am practicing)

The BinaryTreeNode class:

template <class Type>
class BinaryTreeNode: public Node<Type> {
protected:
BinaryTreeNode<Type> *left;
BinaryTreeNode<Type> *right;
BinaryTreeNode<Type> *parent;
public:
BinaryTreeNode<Type>(Type data) : Node<Type>(data) {
    this->left = NULL;
    this->right = NULL;
    this->parent = NULL;
}
~BinaryTreeNode<Type>() {
    delete left;
    delete right;
    delete parent;
}
};

For the Tree:

template <class Type, template <class> class NodeType = BinaryTreeNode>
class BinaryTree {
protected:
    int size;
    NodeType<Type> *root;
public:
    ~BinaryTree<Type, NodeType>() {
        delete root;
    }
    BinaryTree<Type, NodeType>() {
        this->size = 0;
        this->root = NULL;
    }
};

Now in main, I do the following:

BinaryTree<int> *bt = new BinaryTree<int>();
bt->insert(100);
bt->insert(50);
bt->insert(101);

The above works, so far so good.

The insert method/function is where creation of NEW nodes are done. I then tried using each of the following (one by one) and they all result in a segfault (core dump):

delete bt->getRoot();

This resulted in segfault. I then tried

delete bt->getRoot()->getRight();

again segfault. So last I tried

delete bt;

still segfault

I was expecting to simply have memory leaks due to other nodes being unreachable (I am running it with valgrind) but to my surprise, valgrind crashed, and gcc and clang did not even print out any warnings even with -Wall. I need advise on how to do this correctly. Thanks in advance.

Community
  • 1
  • 1

3 Answers3

3

This is going to screw you up

~BinaryTreeNode<Type>() {
    delete left;
    delete right;
    delete parent;
}

Delete the left, then the right. Looks fine. But fails becuase of the next line.
Now you delete the parent. The parents destructor is then called to delete left and right and parent. So by deleting your parent you then call delete on yourself but you are already in the middle of a delete because sombody else tried to call delete. That's not your only problem you enter a recursive loop that is never exited.

Try:

~BinaryTreeNode<Type>() {
    delete left;
    delete right;
}

Parents should delete their children because they own their children.
But children should not delete there parents (as the child does not own the parent).

If you had used C++ techniques rather than C techniques this would have been obvious (and done automatically). Look up std::unique_ptr<>.

PS. Your object is also fundamentally flawed beccause you do not implement the rule of three (five in C++11).

Martin York
  • 257,169
  • 86
  • 333
  • 562
  • Ohh i see. That was all it takes. Its working now. Thanks. I'm not that experienced in C++ yet which is why I'm thinking of deleting every pointer that is in the class, even the parent. –  Aug 05 '13 at 05:06
  • @MarcLee: You should **NOT** be manually deleting pointers. Use smart pointers. I advise you to stop doing it this way. It just leads to bad habits that are hard to break (this is C). Learn the C++ way and use smart pointers. They will call delete automatically for you. – Martin York Aug 05 '13 at 05:08
0

If your invocation order is

delete bt->getRoot();
delete bt->getRoot()->getRight();
delete bt;

Then it will create a problem as you are deleting a node and then invoking a method using the same node itself. The order should be

delete bt->getRoot()->getRight();
delete bt->getRoot();
delete bt;
Saksham
  • 9,037
  • 7
  • 45
  • 73
  • I tried those things one at a time. Each resulted in a segfault. When I tried inserting only one node to the tree, using delete bt did not cause segfault. –  Aug 05 '13 at 04:48
  • We would like to have a look at the insert() method. Also are you sure that the insert() is working fine?? Did you check it? – Saksham Aug 05 '13 at 04:57
  • Ok i'll post it. Not sure if its correct in terms of memory allocation, but in terms of structuring the trees, it works fine. –  Aug 05 '13 at 04:59
0

Either remove delete bt->getRoot()->getRight();(for more memory leaks :) ) or move it to the line before delete bt->getRoot();

dvai
  • 1,953
  • 3
  • 13
  • 15
  • I think the way I mentioned it was confusing. I tried those lines individually and not altogether (sequentially) as I wrote above. I edited the post for better clarity. Basically, I created a tree with height of 1, a parent (root node) and two children (left and right). Deleting any nodes result in segfault. –  Aug 05 '13 at 04:55