4.6 Search

Searching a binary search tree works just the same way as it did before when we were doing it inside an array. We can implement bst_find() immediately:

31. <BST search function 31> =
void *
bst_find (const struct bst_table *tree, const void *item) 
{
  const struct bst_node *p;

  assert (tree != NULL && item != NULL);
  for (p = tree->bst_root; p != NULL; ) 
    {
      int cmp = tree->bst_compare (item, p->bst_data, tree->bst_param);

      if (cmp < 0) 
        p = p->bst_link[0];
      else if (cmp > 0) 
        p = p->bst_link[1];
      else /* cmp == 0 */ 
        return p->bst_data;
    }

  return NULL;
}

This code is included in 29, 145, 196, 489, 522, and 554.

See also:  [Knuth 1998b], section 6.2.2; [Cormen 1990], section 13.2; [Kernighan 1988], section 3.3; [Bentley 2000], chapters 4 and 5, section 9.3, appendix 1; [Sedgewick 1998], program 12.7.