CODEWITHSUNDEEP
c++dynamicbinary-search-tree
Valio
Valio

Reputation: 13

How to delete a BST in C++?

Can someone please help me figure out how to properly delete my bst implementation ? I know it's a simple problem, but i tried everything. I want to avoid declaring a dynamic array and if it is possible keep the code with this pointer structure( no pun intended). The problem lies in the destructor section. Thanks !

    #include<iostream>
    using namespace std;
    struct Tree{
        struct Tree* left;
        struct Tree* right;
        int val;
        Tree(int);
        ~Tree();
        void Print();
    };
    Tree::Tree(int val){
        this->val = val;
        cout<<"insert l/r for node: "<<this->val<<" , type 0 0 - exit"      <<endl;
int l,r;
cin>>l>>r;
if(l and r){
this->left = new Tree(l);
this->right = new Tree(r);
}else if(l==0 and r==0){
    this->left = NULL;
    this->right = NULL;
    return;
}
    }
    Tree::~Tree(){
        if(this->left == NULL and this->right == NULL){
            delete this;
            return;
        }else{
            this->left->~Tree();
            this->right->~Tree();
        }
    }
    void Tree::Print(){
        if(this == NULL) return;
        cout<<this->val<<endl;
        this->left->Print();
        this->right->Print();
    }
    int main(){
        int n;
        cin>>n;
        Tree* newT = new Tree(n);
        newT->Print();
        newT->~Tree();
        //cout<<newT->val<<endl;
        //newT->Print();


    return 0;
    }

Upvotes: 0

Views: 154

Answers (2)

eerorika
eerorika

Reputation: 238471

How to delete a BST in C++?

Assuming the empty children point to null rather than a sentinel object and assuming the nodes were allocated with new, the destructor of a node can be implemented by simply deleting both children:

Tree::~Tree() {
    delete left;
    delete right;
}

if(this == NULL)

This makes little sense. Member functions may not be called on a null pointer.

delete this;

You can not delete this within the destructor. It rarely makes sense to delete this.

newT->~Tree();

You hardly ever should call destructors explicitly. It will not deallocate the memory, which you now leak.

To deallocate the memory that you allocated with new, you must deallocate with delete. This will also call the destructor, so calling it separately would be a mistake.

Upvotes: 0

Some programmer dude
Some programmer dude

Reputation: 409482

There's seldom any need to do delete this, and in a destructor it's actually fatal. The destructor is called because someone already is doing a delete on the object. By doing delete this in the destructor you have an infinite recursion.

Also, don't call the left and right destructors, delete them instead. And of course in the main function you should not call the destructor either, but use delete. The only time you should call a destructor explicitly is when have used placement new, which you haven't done.

There are some other flaws as well, like you never checking if the left or right pointers are null pointers in the Print function.

Lastly, if this is a null pointer, then you have some serious problem elsewhere, so never any need to check for it.

The destructor should simply be

~Tree()
{
    delete left;
    delete right;
}

If you then do delete newT in the main function the whole sub-tree will be automatically deleted.

Upvotes: 2

Related Questions