BST properties and recursive search

Properties of a Binary Search Tree

1. It is a binary tree: every node has at most two children (left and right).
2. All keys in the left subtree of a node are smaller than the node's key.
3. All keys in the right subtree of a node are greater than the node's key (duplicates are usually not allowed, or are always placed on one side).
4. The left and right subtrees are themselves binary search trees.
5. In-order traversal visits the keys in ascending order.
6. Search, insertion and deletion take O(h) time; h = log n for a balanced tree and n for a skewed one.

Recursive search algorithm

Compare the key with the root. If equal, found; if smaller, search the left subtree; otherwise search the right subtree.

Search(node, key)
1. if node = NULL        return NULL          (not found)
2. if key = node->info   return node          (found)
3. if key < node->info   return Search(node->left, key)
4. else                  return Search(node->right, key)

struct node *search(struct node *root, int key) {
    if (root == NULL || root->info == key)
        return root;                       /* empty tree or found */
    if (key < root->info)
        return search(root->left, key);    /* go left */
    return search(root->right, key);       /* go right */
}

Example: BST with root 50 (left 30, right 70; 30 has children 20, 40). Searching 40: 40 < 50 go left; 40 > 30 go right; 40 = 40 found. Three comparisons, one for each node on the path.

Time complexity is O(h): best O(1), average O(log n), worst O(n) for a skewed tree. The recursion depth is also at most h.