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 (struct pbst_traverser *trav) 
{
  assert (trav != NULL);

  if (trav->pbst_node == NULL)
    return pbst_t_first (trav, trav->pbst_table);
  else if (trav->pbst_node->pbst_link[1] == NULL) 
    {
      struct pbst_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;
            return trav->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];
      return trav->pbst_node->pbst_data;
    }
}

This code is included in 504 and 548.

See also:  [Cormen 1990], section 13.2.