4.9.3.3 Starting at the Last Node

The code to start from the greatest node in the tree is analogous to that for starting from the least node. The only difference is that we descend to the right instead:

66. <BST traverser greatest-item initializer 66> =
void *
bst_t_last (struct bst_traverser *trav, struct bst_table *tree) 
{
  struct bst_node *x;

  assert (tree != NULL && trav != NULL);

  trav->bst_table = tree;
  trav->bst_height = 0;
  trav->bst_generation = tree->bst_generation;

  x = tree->bst_root;
  if (x != NULL)
    while (x->bst_link[1] != NULL) 
      {
        if (trav->bst_height >= BST_MAX_HEIGHT) 
          {
            bst_balance (tree);
            return bst_t_last (trav, tree);
          }

        trav->bst_stack[trav->bst_height++] = x;
        x = x->bst_link[1];
      }
  trav->bst_node = x;

  return x != NULL ? x->bst_data : NULL;
}

This code is included in 63.