A binary search tree is a binary tree (see BinaryTrees) in which each node has a key, and a node's key must be greater than all keys in the subtree of its left-hand child and less than all keys in the subtree of its right-hand child. This allows a node to be searched for using essentially the same binary search algorithm used on sorted arrays.

1. Searching for a node

   1 /* returns node with given target key */
   2 /* or null if no such node exists */
   3 Tree
   4 tree_search(Tree root, int target)
   5 {
   6     if(root->key == target) {
   7         return root;
   8     } else if(root->key > target) {
   9         return tree_search(root->left);
  10     } else {
  11         return tree_search(root->right);
  12     }
  13 }

This procedure can be rewritten iteratively, which avoids stack overflow and is likely to be faster:

   1 Tree
   2 tree_search(Tree root, int target)
   3 {
   4     while(root != 0 && root->key != target) {
   5         if(root->key > target) {
   6             root = root->left;
   7         } else {
   8             root = root->right;
   9         }
  10     }
  11 
  12     return root;
  13 }

These procedures can be modified in the obvious way to deal with keys that aren't ints, as long as they can be compared (e.g., by using strcmp on strings).

2. Inserting a new node

As in HashTables, the insertion procedure mirrors the search procedure. We must be a little careful to avoid actually walking all the way down to a null pointer, since a null pointer now indicates a missing space for a leaf that we can fill with our new node. So the code is a little more complex.

   1 void
   2 tree_insert(Tree root, int new_key)
   3 {
   4     Tree new_node;
   5 
   6     new_node = malloc(sizeof(*new_node));
   7     assert(new_node);
   8 
   9     new_node->key = new_key;
  10     new_node->left = 0;
  11     new_node->right = 0;
  12 
  13     for(;;) {
  14         if(root->key > target) {
  15             /* try left child */
  16             if(root->left) {
  17                 root = root->left;
  18             } else {
  19                 /* put it in */
  20                 root->left = new_node;
  21                 return;
  22             }
  23         } else {
  24             /* right child case is symmetric */
  25             if(root->right) {
  26                 root = root->right;
  27             } else {
  28                 /* put it in */
  29                 root->right = new_node;
  30                 return;
  31             }
  32         }
  33     }
  34 }

Note that this code happily inserts duplicate keys. It also makes no attempt to keep the tree balanced. This may lead to very long paths if new keys are inserted in strictly increasing or strictly decreasing order.

3. Costs

Searching for or inserting a node in a binary search tree with n nodes takes

• T(n) ≤ T(k) + O(1)

time, where k is the size of the subtree that contains the target. In BalancedTrees, k will always be at most cn for some constant c < 1. In this case, the recurrence has the solution T(n) = O(log n).

CategoryAlgorithmNotes CategoryProgrammingNotes