Binary search tree visualization

A binary search tree (BST) is a tree in which every node holds one key and has at most two children, a left one and a right one, arranged so that all keys in the left subtree are smaller than the node and all keys in the right subtree are larger or equal. That one rule lets you search, insert and list the keys in order by following a single path from the top.

How it works

The code stores node k at position k of three arrays: its key, its left child and its right child (-1 means no child).

1. Insert: start at the root. If the new key is smaller than the node, go left; otherwise go right. Repeat until the next step would leave the tree, then attach the new node there. An equal key goes right, so duplicates are kept.
2. Search: the same walk. Stop at a node with the key you want, or at an empty place, which means the key is absent.
3. In-order walk: visit the left subtree, then the node, then the right subtree. For a search tree this visits the keys in increasing order, with no sorting.

Time and space complexity

The cost of insert and search is the number of levels you walk down, the height h of the tree.

• Balanced tree, height about log n: each comparison discards about half of the remaining nodes. Keys that arrive in random order give this on average.
• Degenerate tree, height n: every node has one child, so the tree is a linked list and each operation visits every node. This is the worst case.
• In-order walk: O(n), one visit per node.
• Space: O(n), one node per key.

A worked example

Insert the keys 8, 3, 10, 1, 6, 14 and 4 into an empty tree, in that order. For each key the table lists the nodes it was compared with, and where it ended up.

The finished tree is 3 edges tall:

        8
      /   \
     3     10
    / \      \
   1   6      14
      /
     4

Now search for 6. It is compared with 8 (smaller, so go left), with 3 (larger, so go right) and with 6 (equal), which is 3 comparisons for a tree of 7 keys. Walking the tree in order visits 1, 3, 4, 6, 8, 10, 14: sorted, although nothing was ever sorted. Inserting these 7 keys took 11 comparisons.

Order matters. Insert the same kind of keys already sorted, 1 to 7, and every key goes right of the one before: the tree is 6 edges tall, a chain, and the 7 inserts take 21 comparisons.

Pseudocode

The code stores node x in three arrays, so T.key[x], T.left[x] and T.right[x] are its key and its children. NIL is -1 in the code. A smaller key goes left, an equal or larger key goes right.

TREE-INSERT(T, key)
    parent = NIL
    x = T.root
    while x != NIL
        parent = x
        if key < T.key[x]
            x = T.left[x]
        else
            x = T.right[x]
    z = a new node holding key, no children
    if parent == NIL
        T.root = z
    else if key < T.key[parent]
        T.left[parent] = z
    else
        T.right[parent] = z

TREE-SEARCH(T, key)
    x = T.root
    while x != NIL and key != T.key[x]
        if key < T.key[x]
            x = T.left[x]
        else
            x = T.right[x]
    return x                  // NIL if absent

INORDER-WALK(T, x)
    if x != NIL
        INORDER-WALK(T, T.left[x])
        visit T.key[x]
        INORDER-WALK(T, T.right[x])

Insert and search each have one loop that moves down one level per round, so they cost at most the height of the tree. The walk makes one call per node and one more per missing child.

When to use it, and when not to

Use a BST to keep keys ordered while they change: lookups, inserts, and a sorted listing at any time. For a fixed sorted array, binary search is simpler.

Where it is used

• Ordered maps and sets in libraries. Java's TreeMap is documented as a red-black tree, a self-balancing search tree, with guaranteed O(log n) cost for get, put and remove. C++ implementations of std::map and std::set are usually red-black trees too. The tree is what makes sorted iteration and questions like "the smallest key that is at least x" cheap, which a hash table cannot answer.
• Database indexes. Many databases keep ordered indexes in B-trees, a relative of the search tree whose nodes hold many keys so that one node fills a disk page and the tree stays very short. The rule is the same: keys in order, one path from the root to the answer.
• Range queries. To list every key between lo and hi, go down one path to lo and then walk in order until you pass hi. That costs the height plus the number of keys found, and it skips every subtree outside the range.

Variations and related ideas

This lesson has no delete. Deleting a node with two children replaces it with its successor, the smallest key in its right subtree (CLRS, section 12.3). AVL and red-black trees add rotations after each insert or delete to keep the height near log n, and treaps use random priorities for the same purpose. If the keys never change, a sorted array with binary search is simpler. If you only need the smallest key, a binary heap is cheaper, and if you never need order, a hash table is faster on average. The worst case, a chain, behaves like a linked list.