CODEWITHSUNDEEP
c++treedestructorbinary-search-tree
cloud9resident
cloud9resident

Reputation: 157

binary search trees code

wanting to write a destructor for binary search tree (its supposed to delete all the nodes in a tree) here is what i got so far

virtual ~BST() {
  BSTNode<Data>* node = root;
  if (node == NULL){
    return;
  }else if (node->left) {
      while(node->left){
        delete node;
      }
  }else if (node->right){
      while(node->right)
        delete node;
  }
        isize = 0;
}

i know however there is something wrong with the code, how can i fix it

Upvotes: 0

Views: 484

Answers (3)

Some programmer dude
Some programmer dude

Reputation: 409166

When you do e.g.

while(node->left){
    delete node;
}

You delete the node, but do not actually loop to the next one. So the next time in the loop node will not be NULL so you dereference an unallocated data structure which is undefined behavior, and may lead to a crash. And then you try to delete the same node again which is still undefined behavior and may most certainly lead to a crash.

You also won't delete both left and right nodes, only one of them due to the else.

I suggest you put a proper destructor in the BSTNode which deletes its own children:

template<typename T>
BSTNode<T>::~BSTNode()
{
    delete left;
    delete right;
}

Then the destructor of the tree would simply be:

BST::~BST()
{
    delete root;
}

Upvotes: 1

user995502
user995502

Reputation:

Lose the elses. Otherwise if the tree has left. right will not be deleted.

Lose the while. Nodes should have their own destructors and should delete recursively.

Finally lose the ifs. Because delete NULL is valid. 

virtual ~BST() {
  BSTNode<Data>* node = root;
  if (node == NULL){
    return;
  }  
  delete node->left;
  delete node->right;
  isize = 0;
}

Upvotes: 3

Archie
Archie

Reputation: 2672

void BST::deleteNode(BSTNode<Data> *node) {
    if (node) {
        deleteNode(node->left);
        deleteNode(node->right);
        delete node;
    }
}

BST::~BST() {
    deleteNode(root);
}

Upvotes: 3

Related Questions