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:

86. <Destroy a BST iteratively 86> =voidbst_destroy(structbst_table*tree,bst_item_func*destroy)

{structbst_node*stack[BST_MAX_HEIGHT];unsignedcharstate[BST_MAX_HEIGHT];intheight= 0;structbst_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.