GNU libavl 2.0.1
5.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 section 5.9.3 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:
 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) {
<@xref{\NODE\, , Handle case where x.> has a right child,71}
} else {
<@xref{\NODE\, , Handle case where x.> has no right child,72}
}
trav>bst_node = x;
return x>bst_data;
}

This code is included in @refalso{63
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
tailrecursive 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:
 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 @refalso{70
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:
 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 @refalso{70