Thread: How to empty a Binary Serach Tree???

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.

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

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