Binary Search Trees

Basic operations for a complete binary search tree take $O(log n)$ time, worst-case: however, if the tree is just a chain of nodes (effectively a linked list), the same basic operations take $O(n)$ time worst-case.

Nodes in a BST have four properties:

struct Node {
  struct Node* parent;
  struct Node* left;
  struct Node* right;
  int key;
};

The keys of a binary search tree are always stored in a way that satisfies the binary-search-tree property:

Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$ , then $y.key ≤ x.key$ . If $y$ is a node in the right subtree of $x$ , then $y.key ≥ x.key$ .

Because of this property, you can print all the keys in order with a recursive algorithm called inorder tree walk.

Querying

Querying a binary search tree for the minimum, maximum, or a specific key takes $O(h)$ time, where $h$ is the height of the tree:

struct Node* tree_search(struct Node* root, int k) {
  if (!root || root->key == k)
    return root;
  else if (k < root->key)
    return tree_search(root->left, k);
  else
    return tree_search(root->right, k);
}

An iterative version of this algorithm will probably run faster on most computers.

Finding the minimum or maximum is as simple as following the root down it's left or right pointers until the next one is NULL:

struct Node* tree_minimum(struct Node* root) {
  while (root->left)
    root = root->left;
  return root;        
}

struct Node* tree_maximum(struct Node* root) {
  while (root->right)
    root = root->right;
  return root;
}

The successor of a node is next node visited after it in an inorder tree traversal; the predecessor would be the node visit right before it in an inorder tree traversal.

The algorithm for finding the predecessor (or successor) of a node isn't completely trivial. Given a node $x$ , there are two main cases to consider:

If the left subtree is nonempty, then the predecessor is the rightmost node in the left subtree.
If the left subtree is empty, then the predecessor will be the lowest ancestor of $x$ whose left child is also an ancestor of $x$ (this is worth drawing out).

Insertion and deletion

Insertion begins at the root of the tree and walks downward, looking for a NULL child to insert it's node at. It uses a trailing pointer (in this implementation, y) to keep track of the parent:

void tree_insert(struct Tree* tree, struct Node* z) {
  struct Node* x = tree->root;
  struct Node* y = NULL;

  while (x) {
    y = x;
    if (z->key < x->key)
      x = x->left;
    else
      x = x->right;
  }

  z->parent = y;
  
  if (!y) // tree was empty
    tree->root = z;
  else if (z->key < y->key)
    y->left = z;
  else
    y->right = z;
}

Deleting a node $z$ from a tree $T$ is solidly trickier than insertion, but it nicely divides into three situations:

If $z$ has no children, just make its parents pointer to it NULL.
If $z$ has one child, promote that child to take its place (make $z$ 's parent point to $z$ 's child, and make its child point to its parent).
If $z$ has two children,