4.9.3.7 Advancing to the Next Node

The algorithm of bst_t_next(), the function for finding a successor, divides neatly into three cases. Two of these are the ones that we discussed earlier in the introduction to this kind of traverser (see Better Iterative Traversal). The third case occurs when the last node returned was NULL, in which case we return the least node in the table, in accordance with the semantics for libavl tables. The function outline is this:

71. <BST traverser advance function 71> =
void *
bst_t_next (struct bst_traverser *trav) 
{
  struct bst_node *x;

  assert (trav != NULL);

  if (trav->bst_generation != trav->bst_table->bst_generation)
    trav_refresh (trav);

  x = trav->bst_node;
  if (x == NULL) 
    {
      return bst_t_first (trav, trav->bst_table);
    } 
  else if (x->bst_link[1] != NULL) 
    {
      <Handle case where x has a right child 72>
    } 
  else 
    {
      <Handle case where x has no right child 73>
    }
  trav->bst_node = x;

  return x->bst_data;
}

This code is included in 64.

The case where the current node has a right child is accomplished by stepping to the right, then to the left until we can't go any farther, as discussed in detail earlier. The only difference is that we must check for stack overflow. When stack overflow does occur, we recover by calling trav_balance(), then restarting bst_t_next() using a tail-recursive call. The tail recursion will never happen more than once, because trav_balance() ensures that the tree's height is small enough that the stack cannot overflow again:

72. <Handle case where x has a right child 72> =
if (trav->bst_height >= BST_MAX_HEIGHT) 
  {
    bst_balance (trav->bst_table);
    return bst_t_next (trav);
  }

trav->bst_stack[trav->bst_height++] = x;
x = x->bst_link[1];

while (x->bst_link[0] != NULL) 
  {
    if (trav->bst_height >= BST_MAX_HEIGHT) 
      {
        bst_balance (trav->bst_table);
        return bst_t_next (trav);
      }

    trav->bst_stack[trav->bst_height++] = x;
    x = x->bst_link[0];
  }

This code is included in 71.

In the case where the current node has no right child, we move upward in the tree based on the stack of parent pointers that we saved, as described before. When the stack underflows, we know that we've run out of nodes in the tree:

73. <Handle case where x has no right child 73> =
struct bst_node *y;

do 
  {
    if (trav->bst_height == 0) 
      {
        trav->bst_node = NULL;
        return NULL;
      }

    y = x;
    x = trav->bst_stack[--trav->bst_height];
  } 
while (y == x->bst_link[1]);

This code is included in 71.