4.10.2 Iterative Copying       Now we can factor out the recursion, starting with the tail recursion. This process is very similar to what we did with the traversal code, so the details are left for Exercise 1. Let's look at the results part by part:

79. <Iterative copy of BST 79> =
/* Copies org to a newly created tree, which is returned. */
struct bst_table *
bst_copy_iterative (const struct bst_table *org)
{ struct bst_node *stack[2 * (BST_MAX_HEIGHT + 1)];
/* Stack. */ int height = 0; /* Stack height. */

This time, our stack will have two pointers added to it at a time, one from the original tree and one from the copy. Thus, the stack needs to be twice as big. In addition, we'll see below that there'll be an extra item on the stack representing the pointer to the tree's root, so our stack needs room for an extra pair of items, which is the reason for the “+ 1” in stack[]'s size.

80. <Iterative copy of BST 79> +=
struct bst_table *new;             /* New tree. */
const struct bst_node *x;          /* Node currently being copied. */
struct bst_node *y;                /* New node being copied from x. */

new = bst_create (org->bst_compare, org->bst_param, org->bst_alloc);
new->bst_count = org->bst_count;
if (new->bst_count == 0)
return new;

x = (const struct bst_node *) &org->bst_root;
y = (struct bst_node *) &new->bst_root;

This is the same kind of “dirty trick” already described in Exercise 4.7-1.

81. <Iterative copy of BST 79> +=
for (;;)
= org->bst_alloc->libavl_malloc (org->bst_alloc, sizeof *y->bst_link); stack[height++] = (struct bst_node *) x; stack[height++] = y; x = x->bst_link; y = y->bst_link; } y->bst_link = NULL;

This code moves x down and to the left in the tree until it runs out of nodes, allocating space in the new tree for left children and pushing nodes from the original tree and the copy onto the stack as it goes. The cast on x suppresses a warning or error due to x, a pointer to a const structure, being stored into a non-constant pointer in stack[]. We won't ever try to store into the pointer that we store in there, so this is legitimate.

We've switched from using malloc() to using the allocation function provided by the user. This is easy now because we have the tree structure to work with. To do this earlier, we would have had to somehow pass the tree structure to each recursive call of the copy function, wasting time and space.

82. <Iterative copy of BST 79> +=
for (;;)
{ y->bst_data = x->bst_data; if (x->bst_link != NULL)