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(structbst_traverser*trav)

{structbst_node*x;assert(trav!=NULL);if(trav->bst_generation!=trav->bst_table->bst_generation)trav_refresh(trav);x=trav->bst_node;if(x==NULL)

{returnbst_t_first(trav,trav->bst_table); }

elseif(x->bst_link[1] !=NULL)

{ <Handle case wherexhas a right child 72> }

else

{ <Handle case wherexhas no right child 73> }trav->bst_node=x;returnx->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 wherexhas a right child 72> =if(trav->bst_height>=BST_MAX_HEIGHT)

{bst_balance(trav->bst_table);returnbst_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);returnbst_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 wherexhas no right child 73> =structbst_node*y;do

{if(trav->bst_height== 0)

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

This code is included in 71.