13.5.5 Advancing to the Next Node |

There are the same three cases for advancing a traverser as the other types of binary trees that we've already looked at. Two of the cases, the ones where we're starting from the null item or a node that has a right child, are unchanged.

The third case, where the node that we're starting from has no right child, is the case that must be revised. We can use the same algorithm that we did for ordinary BSTs without threads or parent pointers, described earlier (see Better Iterative Traversal). Simply put, we move upward in the tree until we move up to the right (or until we move off the top of the tree).

The code uses *q* to move up the tree and *p* as *q*'s child, so the
termination condition is when *p* is *q*'s left child or *q* becomes a
null pointer. There is a non-null successor in the former case, where
the situation looks like this:

509. <PBST traverser advance function 509> =void*pbst_t_next(structpbst_traverser*trav)

{assert(trav!=NULL);if(trav->pbst_node==NULL)returnpbst_t_first(trav,trav->pbst_table);elseif(trav->pbst_node->pbst_link[1] ==NULL)

{structpbst_node*q, *p; /* Current node and its child. */for(p=trav->pbst_node,q=p->pbst_parent; ;

p=q,q=q->pbst_parent)if(q==NULL||p==q->pbst_link[0])

{trav->pbst_node=q;returntrav->pbst_node!=NULL?trav->pbst_node->pbst_data:NULL; } }

else

{trav->pbst_node=trav->pbst_node->pbst_link[1];while(trav->pbst_node->pbst_link[0] !=NULL)trav->pbst_node=trav->pbst_node->pbst_link[0];returntrav->pbst_node->pbst_data; } }

This code is included in 504 and 548.

**See also:**
[Cormen 1990], section 13.2.