Binary Search Tree Destructor

Question

Working on implementing my own BST in C++ for the experience of dealing with such structures.

I've had trouble implementing a destructor. I found in my studies, that one can't really have a recursive destructor (due to a flag that doesn't allow the destructor to be called on the same object after having been called), but I'm not really sure of any other way to successfully clean up all the nodes in the tree.

To compensate, I've created a helper function - however this throws an unresolved external error on the 'delete n' line. Any tips?

Code:

void BinSearchTree::Clear(tNode* n)
{
    if (n->left != NULL)
        Clear(n->left);
    if (n->right != NULL)
        Clear(n->right);
    delete n;
    n = NULL;
    size--;
}

Its has nothing to do with the problem, but you don't need to set the variable `n` to NULL, since it's not accessed any more in the function. — Some programmer dude, Nov 05 '11 at 06:59
@JoachimPileborg The null state is set just because Clear can be called independently of the destructor to reset the tree. I was originally testing for a lack of a valid root pointer to determine if the tree was initialized, prior to having a size data member to keep track of such things. — DivinusVox, Nov 05 '11 at 07:08
Out of curiosity, does anyone know if size is generally a tracked value in standard implementations of trees? I see little use for it, since an iterative loop isn't realistic on the model. — DivinusVox, Nov 05 '11 at 07:10
The variable `n` is local to the this function. Setting it to NULL in the function will not set it to NULL outside the function, then you need to pass `n` either as a reference to a pointer(`tNode *&`) or as a pointer to a pointer (`tNode **`). — Some programmer dude, Nov 05 '11 at 07:15
Recursion on the type level is generally not a problem. Otherwise, we couldn't have node-based structures to begin with :) — fredoverflow, Nov 05 '11 at 07:30
@avakar - No, the tree is only linked downward as I'm building it currently. — DivinusVox, Nov 05 '11 at 07:36

Jeremy Friesner · Accepted Answer · 2011-11-05T07:04:51.607

21

You can have a recursive destructor; what you can't do is delete the same object twice.

A typical way to delete a tree in C++ might be something like this:

BinSearchTree::~BinSearchTree()
{
   delete _rootNode;  // will recursively delete all nodes below it as well
}

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

Regarding the unresolved external error -- is that error thrown when you try to compile/link the program? If so, it's probably because the code for the tNode class (and in particular the tNode destructor, if you declared one) doesn't exist or isn't getting compiled into your project.

edited Nov 05 '11 at 07:04

answered Nov 05 '11 at 06:59

Jeremy Friesner

70,199
15
131
234

This may seem like a stupid need for clarification, but I must ask because this is unlike any recursion I've seen. Is this method of recursion still worse than a while loop when dealing with a linked list? – Logan Kling Nov 21 '15 at 05:30
For a linked list I'd probably just use the while loop, since it's just as easy to write correctly and to understand as doing it recursively, and it uses a fixed amount of stack space. Trees, on the other hand, are much easier to deal with via recursion than by using iterative methods -- if you write a non-recursive method to walk a tree, you usually end up implementing your own stack anyway. – Jeremy Friesner Apr 20 '16 at 15:18
What if the stack overflows? – May 03 '18 at 19:33
Then your program will crash or exhibit some other form of undefined behavior. – Jeremy Friesner May 03 '18 at 19:56

score 4 · Answer 2 · answered Nov 05 '11 at 07:43

Previous answers have pointed out that the unresolved external error is likely caused by a tNode destructor that is declared but not defined in a translation unit that the linker can see.

However, you have a second error: You appear to believe that setting n to null does something it doesn't do. The pointer value n is passed by value, not by reference, such that changing its value (e.g. by assigning NULL) has no effect after the function returns.

This will probably give you errors when you clear the tree and expect the root node pointer to have been set to NULL, when it remains a dangling pointer to freed memory. The result will be runtime error, not your linker error.

void BinSearchTree::Clear(tNode **N)
{
    tNode * n = *N;
    if (n->left != NULL)
        Clear(n->left);
    if (n->right != NULL)
        Clear(n->right);
    delete n;
    *N = NULL;
    size--;
}

Will do what you expect.

score 3 · Answer 3 · answered Nov 05 '11 at 07:03

The problem is that in you class you probably declared that the node structure has a custom destructor, but you don't provide it so at link time the compiler is complaining a piece is missing.

If you don't need any more custom code in the destructor then you can just remove the destructor from the struct declaration and your program will compile fine.

Note however that there is no problem at all to have a destructor of to destory children nodes (see Brendan Long answer). If you ran into problems while attempting that the issue you faced must me something else.

score 2 · Answer 4 · edited May 23 '17 at 12:02

2

Just use a destructors. It sounds like your problem is that you were trying to call the destructors directly, but the language handles this for you. They're called either when you leave a stack allocated object's scope, or when you delete an object.

All you should need is this:

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

delete will call their destructors.

Note: It's perfectly safe to delete NULL, it has no effect.

edited May 23 '17 at 12:02

Community

1
1

answered Nov 05 '11 at 06:57

Brendan Long

53,280
21
146
188

@JeremyFriesner - You're right. Sorry, must be more tired than I thought. – Brendan Long Nov 05 '11 at 07:04
Yeah just fixed that too. Needed to look it up to make sure it was safe since I don't do C++ very often. – Brendan Long Nov 05 '11 at 07:07

Martin York · Answer 5 · 2011-11-05T11:15:49.513

1

How about automating it:

class BinSearchTree
{
    std::auto_ptr<tNode>   left;
    std::auto_ptr<tNode>   right;

    BinSearchTree(BinSearchTree const&);
    BinSearchTree& operator=(BinSearchTree const&); // private
};

Now destruction is automatic. :-)

edited Nov 05 '11 at 11:15

answered Nov 05 '11 at 07:07

Martin York

257,169
86
333
562

Only if you have C++11 turned on. std::auto_ptr is perfect for this. – Martin York Nov 05 '11 at 07:24
1

If you assign one binary search tree to another, the children will be kidnapped. Is that really what you want? – fredoverflow Nov 05 '11 at 07:31
Better kidnapped than cloned. By implication the BinSearchTree already has copy construcctor and assignment operator defined (otherwise the RAW pointers would be cloned thus leading to double delete). So I made the assumption that they were defined, but even if they are not this technique may allow kidnap but this is better than being cloned. – Martin York Nov 05 '11 at 11:23

score 0 · Answer 6 · answered Oct 29 '17 at 00:41

0

You can also use recursion, you just need to change the function header to:

void remove(node*& root)

and it will work.

answered Oct 29 '17 at 00:41

Muhammad Abdullah Aziz

3
5

Binary Search Tree Destructor

6 Answers6

Linked

Related