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.

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.

>>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.

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???

>>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.

...
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

...
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.

>>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)