4.9.2.1 Improving Convenience

Now we can work on improving the convenience of our traversal function. But, first, perhaps it's worthwhile to demonstrate how inconvenient it really can be to use walk(), regardless of how it's implemented internally.

Suppose that we have a BST of character strings and, for whatever reason, want to know the total length of all the strings in it. We could do it like this using walk():

57. <Summing string lengths with walk() 57> =
static void 
process_node (void *data, void *param) 
{
  const char *string = data;
  size_t *total = param;

  *total += strlen (string);
}

size_t 
total_length (struct bst_table *tree) 
{
  size_t total = 0;
  walk (tree, process_node, &total);
  return total;
}

With the functions first_item() and next_item() that we'll write in this section, we can rewrite these functions as the single function below:

58. <Summing string lengths with next_item() 58> =
size_t 
total_length (struct bst_table *tree) 
{
  struct traverser t;
  const char *string;
  size_t total = 0;

  for (string = first_item (tree, &t); string != NULL; string = next_item (&t))
    total += strlen (string);
  return total;
}

You're free to make your own assessment, of course, but many programmers prefer the latter because of its greater brevity and fewer “unsafe” conversions to and from void pointers.

Now to actually write the code. Our task is to modify traverse_iterative() so that, instead of calling action, it returns node->bst_data. But first, some infrastructure. We define a structure to contain the state of the traversal, equivalent to the relevant argument and local variables in traverse_iterative(). To emphasize that this is not our final version of this structure or the related code, we will call it struct traverser, without any name prefix:

59. <Iterative traversal of BST, take 6 59> =
struct traverser 
  {
    struct bst_table *table;                  /* Tree being traversed. */
    struct bst_node *node;                    /* Current node in tree. */
    struct bst_node *stack[BST_MAX_HEIGHT];   /* Parent nodes to revisit. */
    size_t height;                            /* Number of nodes in stack. */
  };

See also 60 and 61.

Function first_item() just initializes a struct traverser and returns the first item in the tree, deferring most of its work to next_item():

60. <Iterative traversal of BST, take 6 59> +=
/* Initializes trav for tree.
   Returns data item in tree with the smallest value, 
   or NULL if tree is empty.
   In the former case, next_item() may be called with trav
   to retrieve additional data items. */
void *
first_item (struct bst_table *tree, struct traverser *trav) 
{
  assert (tree != NULL && trav != NULL);
  trav->table = tree;
  trav->node = tree->bst_root;
  trav->height = 0;
  return next_item (trav);
}

Function next_item() is, for the most part, a simple modification of traverse_iterative():

61. <Iterative traversal of BST, take 6 59> +=
/* Returns the next data item in inorder 
   within the tree being traversed with trav,
   or if there are no more data items returns NULL. 
   In the former case next_item() may be called again 
   to retrieve the next item. */
void *
next_item (struct traverser *trav) 
{
  struct bst_node *node;

  assert (trav != NULL);
  node = trav->node;
  while (node != NULL) 
    {
      if (trav->height >= BST_MAX_HEIGHT) 
        {
          fprintf (stderr, "tree too deep\n");
          exit (EXIT_FAILURE);
        }

      trav->stack[trav->height++] = node;
      node = node->bst_link[0];
    }

  if (trav->height == 0)
    return NULL;

  node = trav->stack[--trav->height];
  trav->node = node->bst_link[1];
  return node->bst_data;
}

See also:  [Knuth 1997], algorithm 2.3.1T; [Knuth 1992], p. 50–54, section “Recursion Elimination” within article “Structured Programming with go to statements”.

Exercises:

1. Make next_item() reliable by providing alternate code to execute on stack overflow. This code will work by calling bst_balance() to “balance” the tree, reducing its height such that it can be traversed with the small stack that we use. We will develop bst_balance() later. For now, consider it a “black box” that simply needs to be invoked with the tree to balance as an argument. Don't forget to adjust the traverser structure so that later calls will work properly, too. [answer]

2. Without modifying next_item() or first_item(), can a function prev_item() be written that will move to and return the previous item in the tree in inorder? [answer]