4.11.3 Aside: Iterative Destruction

As we've done before for other algorithms, we can factor the recursive destruction algorithm into an equivalent iteration. In this case, neither recursive call is tail recursive, and we can't easily modify the code so that it is. We could still factor out the recursion by our usual methods, although it would be more difficult, but this problem is simple enough to figure out from first principles. Let's do it that way, instead, this time.

The idea is that, for the tree's root, we traverse its left subtree, then its right subtree, then free the root. This pattern is called a postorder traversal (see postorder traversal).

Let's think about how much state we need to keep track of. When we're traversing the root's left subtree, we still need to remember the root, in order to come back to it later. The same is true while traversing the root's right subtree, because we still need to come back to free the root. What's more, we need to keep track of what state we're in: have we traversed the root's left subtree or not, have we traversed the root's right subtree or not?

This naturally suggests a stack that holds two-part items (root, state), where root is the root of the tree or subtree and state is the state of the traversal at that node. We start by selecting the tree's root as our current node p, then pushing (p, 0) onto the stack and moving down to the left as far as we can, pushing as we go. Then we start popping off the stack into (p, state) and notice that state is 0, which tells us that we've traversed p's left subtree but not its right. So, we push (p, 1) back onto the stack, then we traverse p's right subtree. When, later, we pop off that same node back off the stack, the 1 tells us that we've already traversed both subtrees, so we free the node and keep popping. The pattern follows as we continue back up the tree.

That sounds pretty complicated, so let's work through an example to help clarify. Consider this binary search tree:

Abstractly speaking, we start with 4 as p and an empty stack. First, we work our way down the left-child pointers, pushing onto the stack as we go. We push (4, 0), then (2, 0), then (1, 0), and then p is NULL and we've fallen off the bottom of the tree. We pop the top item off the stack into (p, state), getting (1, 0). Noticing that we have 0 for state, we push (1, 1) on the stack and traverse 1's right subtree, but it is empty so there is nothing to do. We pop again and notice that state is 1, meaning that we've fully traversed 1's subtrees, so we free node 1. We pop again, getting 2 for p and 0 for state. Because state is 0, we push (2, 1) and traverse 2's right subtree, which means that we push (3, 0). We traverse 3's null right subtree (again, it is empty so there is nothing to do), pushing and popping (3, 1), then free node 3, then move back up to 2. Because we've traversed 2's right subtree, state is 1 and p is 2, and we free node 2. You should be able to figure out how 4 and 5 get freed.

A straightforward implementation of this approach looks like this:

87. <Destroy a BST iteratively 87> =
void 
bst_destroy (struct bst_table *tree, bst_item_func *destroy) 
{
  struct bst_node *stack[BST_MAX_HEIGHT];
  unsigned char state[BST_MAX_HEIGHT];
  int height = 0;

  struct bst_node *p;

  assert (tree != NULL);
  p = tree->bst_root;
  for (;;) 
    {
      while (p != NULL) 
        {
          if (height >= BST_MAX_HEIGHT) 
            {
              fprintf (stderr, "tree too deep\n");
              exit (EXIT_FAILURE);
            }
          stack[height] = p;
          state[height] = 0;
          height++;

          p = p->bst_link[0];
        }

      for (;;) 
        {
          if (height == 0) 
            {
              tree->bst_alloc->libavl_free (tree->bst_alloc, tree);
              return;
            }

          height--;
          p = stack[height];
          if (state[height] == 0) 
            {
              state[height++] = 1;
              p = p->bst_link[1];
              break;
            } 
          else 
            {
              if (destroy != NULL && p->bst_data != NULL)
                destroy (p->bst_data, tree->bst_param);
              tree->bst_alloc->libavl_free (tree->bst_alloc, p);
            }
        }
    }
}

See also:  [Knuth 1997], exercise 13 in section 2.3.1.