13.5.6 Backing Up to the Previous Node

This is the same as advancing a traverser, except that we reverse the directions.

508. <PBST traverser back up function 508> =
void *
pbst_t_prev (struct pbst_traverser *trav) 
{
  assert (trav != NULL);

  if (trav->pbst_node == NULL)
    return pbst_t_last (trav, trav->pbst_table);
  else if (trav->pbst_node->pbst_link[0] == 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[1]) 
          {
            trav->pbst_node = q;
            return trav->pbst_node != NULL ? trav->pbst_node->pbst_data : NULL;
          }
    } 
  else 
    {
      trav->pbst_node = trav->pbst_node->pbst_link[0];
      while (trav->pbst_node->pbst_link[1] != NULL)
        trav->pbst_node = trav->pbst_node->pbst_link[1];
      return trav->pbst_node->pbst_data;
    }
}

This code is included in 502 and 546.

See also:  [Cormen 1990], section 13.2.