Destructor for BST

Question

I have to implement my own Binary Search Tree. As far as I know everything works fine, except destructors. Here is some code(all destructors and constructors)

Node(){
        val = T();
        parent=nullptr;
        lChild = nullptr;
        rChild = nullptr;
    }
    Node(T &valx){
        val=valx;
        parent=nullptr;
        lChild = nullptr;
        rChild = nullptr;
    }
    Node(const Node &other){
        val = other.val;
        if(other.lChild!=nullptr){
            lChild = new Node(*other.lChild);
            lChild->parent=this;
        }
        else
            lChild=nullptr;
        if(other.rChild!=nullptr){
            rChild= new Node(*other.rChild);
            rChild->parent=this;
        }
        else
            rChild=nullptr;
    }
    ~Node(){
        if(lChild!=nullptr){
            delete lChild; 
            lChild=nullptr; 
        }
        if(rChild!=nullptr){
            delete rChild; 
            rChild=nullptr; 
        }
    }

and

Set(){
    root = nullptr;
    sizeOfTree=0;
}
Set(const Set &other){
    if(other.root!=nullptr){
        root = new Node(*other.root);
        root->parent=nullptr;
    }
    else
        root=nullptr;
    sizeOfTree=other.sizeOfTree;
}
~Set()
{
    if(root!=nullptr){
        delete root;
        //root->~Node();
        root=nullptr;
    }
}

With the simpliest test, valgrind shows 272 errors. Thanks for help

@edit: part of valgrind output:

==6981== Invalid read of size 8
==6981==    at 0x405C29: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:53)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x404790: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x4015F0: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c34468 is 24 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4015A6: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid read of size 8
==6981==    at 0x405C5F: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:57)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x404790: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x4015F0: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c34470 is 32 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4015A6: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid free() / delete / delete[] / realloc()
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x404790: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x4015F0: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c34450 is 0 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4015A6: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid read of size 8
==6981==    at 0x405C6C: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:58)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x4057AF: Set<Pionek>::clear() (JakbyGomoku4.cpp:222)
==6981==    by 0x40160B: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:731)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c334c0 is 32 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4016DE: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:742)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid write of size 8
==6981==    at 0x405C89: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:59)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x4057AF: Set<Pionek>::clear() (JakbyGomoku4.cpp:222)
==6981==    by 0x40160B: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:731)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c334c0 is 32 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4016DE: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:742)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid read of size 8
==6981==    at 0x405C36: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:54)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x40479C: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x401755: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:748)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c33448 is 24 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401DF0: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:314)
==6981==    by 0x4016DE: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:742)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid write of size 8
==6981==    at 0x405C53: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:55)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x40479C: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x401755: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:748)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c33448 is 24 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401DF0: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:314)
==6981==    by 0x4016DE: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:742)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)

Please share valgrind output – Saqlain Apr 13 '13 at 09:06 — Saqlain, Apr 13 '13 at 09:06
Rule of Three... Rule of Three... Rule of Three... – Alex Chamberlain Apr 13 '13 at 09:41 — Alex Chamberlain, Apr 13 '13 at 09:41

score 1 · Accepted Answer · edited May 23 '17 at 12:12

1

You are missing operator= in addition to copy ctor and destructor check here
Also there is no need to check for nullptr in destructor, it is ok to delelete nullptr.
Consider something like

Node n1;
//set children for n1
{
Node n2;
//set children for n2
n1 = n2;//Now both n1 and n2 points same children, and initial children of n1 becomes mem leak
}//n2 destructor deletes its children leaving n1 pointing to the same already freed memory location

edited May 23 '17 at 12:12

Community

1
1

answered Apr 13 '13 at 09:06

alexrider

4,449
1
17
27

For Node, Set or both? Any hint how it should look like? – Krever Apr 13 '13 at 09:17
For both as both have destructor and copy ctor. Check first link I posted, it already contains detailed explanations and examples. – alexrider Apr 13 '13 at 09:23
Accroding to reports you have posted this is the problem. You crate node, assign one node to another and as result got 2 nodes pointing to the same memory location, once one of them deleted remaining one will hold pointers to the already freed memory. – alexrider Apr 13 '13 at 09:25
I ve looked into this topic and if I understand correctly my operator= should do destructors work if this!=that and then do copy constructor work. Am I right? – Krever Apr 13 '13 at 09:38
Right, since object you are assigning to need to pick it's data from other one. Thus deleting old data and replacing it with whatever you will got from that. – alexrider Apr 13 '13 at 09:44
Okay, thanks a lot. Operator= solve all my problems and reduced 272 errors to 0. You are great. Thanks. – Krever Apr 13 '13 at 10:15

Destructor for BST

1 Answers1