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:

78. <Iterative copy of BST 78> =
/* 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. */

See also 79, 80, and81.

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.

79. <Iterative copy of BST 78> +=
  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.

80. <Iterative copy of BST 78> +=
  for (;;) 
    {
      while (x->bst_link[0] != NULL) 
        {
          y->bst_link[0] 
            = org->bst_alloc->libavl_malloc (org->bst_alloc,
                                             sizeof *y->bst_link[0]);
          stack[height++] = (struct bst_node *) x;
          stack[height++] = y;
          x = x->bst_link[0];
          y = y->bst_link[0];
        }
      y->bst_link[0] = 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.

81. <Iterative copy of BST 78> +=
      for (;;) 
        {
          y->bst_data = x->bst_data;

          if (x->bst_link[1] != NULL) 
            {
              y->bst_link[1] = 
                org->bst_alloc->libavl_malloc (org->bst_alloc,
                                              sizeof *y->bst_link[1]);
              x = x->bst_link[1];
              y = y->bst_link[1];
              break;
            }
          else 
            y->bst_link[1] = NULL;

          if (height <= 2)
            return new;

          y = stack[–height];
          x = stack[–height];
        }
    }
}

We do not pop the bottommost pair of items off the stack because these items contain the fake struct bst_node pointer that is actually the address of bst_root. When we get down to these items, we're done copying and can return the new tree.

See also:  [Knuth 1997], algorithm 2.3.1C; [ISO 1990], section 6.5.2.1.

Exercises:

1. Suggest a step between bst_copy_recursive_2() and bst_copy_iterative(). [answer]