# How to empty a Binary Serach Tree???

Printable View

• 01-27-2003
ripper079
How to empty a Binary Serach Tree???
Well Iīve been working with this Binary Search Tree and it is almost completed. Itīs actually only missing a "cleaning" operation. I am trying to implement a member-fuction for cleanup that actually deletes all nodes in the tree for avoiding a serius memory leak. The problem is that I donīt know how to do it.

I have one solution that deletes the root until the tree is empty but this seems quite un-efficient because the tree must be rebuild every time it deletes the root. I was also thinking to implement a recusive deleteAllNodes member-func but isnīt this also quite un-efficient if the tree contains MANY nodes (invokes many functions)???. Iīm looking for an iterative solution (if there is any) but I havenīt come up with some.
• 01-27-2003
ggs
If you're that worried about stack depth, you can treat the binary tree as a list that _may_ have other lists sprout off the side. Iterate through all the right nodes, and recurse for left nodes. I think this will reduce the stack depth.
• 01-27-2003
Cela
>>I have one solution that deletes the root until the tree is empty
Eew, yucky! Why not just use an in-order traversal and instead of doing something fun with the node, delete it. :-)
Code:

```void destroy(tree *t) {   if (t == 0)   {     return;   }   destroy(t->left);   destroy(t->right);   delete t; }```
>>but isnīt this also quite un-efficient if the tree contains MANY nodes (invokes many functions)???.
Not enough to worry about unless you've fallen into the worst case of ordered insertion where the tree depth is equal to the number of nodes. If this is even close to possible you need to use a balanced insertion algorithm to begin with. Otherwise, a recursive routine only has a depth equal to the height of the tree. Even for **HUGE** trees this won't be noticeable.
• 01-28-2003
ripper079
Yeeh I guess that a recursive deletenode-func would be the best solution for empting the tree. But this araises a new question for me. Iīve always tried to avoid recursive functions because I found it very un-efficient e.i. Fibonacci problem can be solved much better with an iterative (for loop) solution.

Because of mine dislike for recursion Iīve replaced it with a iteratiove solution when possible. For example in my insert and remove methods Iīve iterated "down" to the node that should be preformed an action where I easily could use recursion insteed. Is my "dislike" for recusion unjustyfied???
• 01-28-2003
Cela
>>Is my "dislike" for recusion unjustyfied???
Not a bit :-) For the most part recursive functions are better implemented iteratively, but recursion does have it's place for some recursively defined data structures or algorithms. Most of the time a binary tree is made recursively because it's much simpler, more natural, and the efficiency hit isn't that bad. quicksort and mergesort are defined recursively and most easily written that way as well. If you need blazing speed and a small stack depth the you can write them iteratively, but if you've ever done that you'll find it's a lot of extra work and complexity for not a whole lot of performance improvement.

Recursion should be the last choice except in a few well defined application areas where recursion has been proven to be a very small handicap in performance and a huge timesaver in creation and maintenance.
• 01-28-2003
ripper079
Quote:

...
but if you've ever done that you'll find it's a lot of extra work and complexity for not a whole lot of performance improvement.
I know exactly what you mean. Well I thought that it would be big performence bootleneek because of my earlier experience with recursion. Well maybe next time a should make it easier for me insteed of looking at the perfomace issue. After all you can always modify (or rebuild the whole structure:( ) it later.

Also I was a little confused by your earlier statement
Quote:

...
Otherwise, a recursive routine only has a depth equal to the height of the tree.
Shouldnīt it be "Otherwise, a recursive routine only has a depth equal to the height times 2 of the tree" because you actually compare the links(leftchild and rightchild) ??? I presume you mean the number of times the actual function is invoked?!?! Need confirmation on this subject.
• 01-29-2003
Cela
>>Need confirmation on this subject.
Consider a tree with height 4
Code:

```          6           / \     4          9   /  \      /  \   2    5    7    10  / \  / \  / \  / \ 0  1                11```
The most recursive calls you'll make for a search/deletion is 4, including the first call. To begin an in-order search you start by going to a depth of 4, (6 4 2 0), then return to a stack depth of 3 and recurse to 4 again. The whole order is (6 4 2 0 2 1 2 4 5 4 6 9 7 9 10 11)