A binary search tree (BST) is a binary tree where every node in the left subtree is less than the root, and every node in the right subtree is of a value greater than the root. The properties of a binary search tree are recursive: if we consider any node as a “root,” these properties will remain true.

Binary search tree of the keys 1 to 7 rooted at 4, with its in-order traversal 1 2 3 4 5 6 7
Smaller keys go left and larger keys go right at every node, so an in-order walk lists the keys sorted.

Due to the way nodes in a binary search tree are ordered, an in-order traversal (left node, then root node, then right node) will always produce a sequence of values in increasing numerical order.

Searching

Binary search trees are called “search trees” because they make searching for a certain value more efficient than in an unordered tree. In an ideal binary search tree, we do not have to visit every node when searching for a particular value.

Here is how we search in a binary search tree:

  1. Begin at the tree’s root node
  2. If the value is smaller than the current node, move left
  3. If the value is larger than the current node, move right
Searching for 3: compare with 4 and go left, compare with 2 and go right, find 3
A search makes one comparison per level and follows a single path down from the root.

Inserting

New nodes in a binary search tree are always added at a leaf position. Performing a search can easily find the position for a new node.

Inserting 8: the search goes 4, 6, 7 and finds the empty right child of 7, where 8 is added as a new leaf
Insert searches for the key, falls off the tree, and hangs the new node there as a leaf.

Removing

When removing from a binary search tree, we are concerned with keeping the rest of the tree in the correct order. This means removing is different depending on whether the node we are removing has children. There are three cases:

If the node being removed is a leaf, it can simply be deleted.

Removing the leaf 3: before, 3 is crossed out under 2; after, 2 has only its left child 1
A leaf has nothing below it, so removing it only clears its parent's pointer.

If the node has a single child, (left or right) we must move the child into the position of the node when deleting it.

Removing 7, whose only child is 8: 8 moves up and becomes the right child of 6
A node with one child is replaced by that child, and the order of the keys does not change.

If the node has two children, we must first find the In-Order Predecessor (IOP): the largest node in our node’s left subtree. The IOP never has a right child (it may have a left child), and can be found by starting at the left subtree’s root and moving right as far as possible. We can then swap the node being removed with its IOP and delete it from the IOP's old position, where it is now a leaf or has one child, one of the two easy cases above.

Removing 4, which has two children: swap it with its in-order predecessor 3, then delete it as a leaf
A node with two children swaps keys with its in-order predecessor, then is removed from the predecessor's old place (here a leaf).

Runtime and BSTs

Depending on the values contained in a binary search tree, and the order in which they are added, the performance of a BST’s operations can vary. This performance depends on the shape of the tree and the number of nodes it contains.

In an ideal case, a binary search tree has a similar number of nodes in its right and left subtrees. Since you have to visit less nodes when searching in an ideal BST, this case has a run time of O(lg(n)) for all operations that utilize find, including search, insert, and remove.

A balanced binary search tree of the keys 1 to 7: root 4, height 3
In a balanced tree the height is about log₂ n, so every operation that searches is O(log n).

The worst case of a binary search tree is one that has its values added in numerical order. This structure then doesn’t resemble a tree - it looks like a linked list! As potentially every node has to be visited when searching, the worst case BST has a run time of O(n) for all operations utilizing find.

An unbalanced binary search tree of 1 to 5 that is just a chain, like a linked list
Inserting keys in sorted order builds a chain of height n, so every operation becomes O(n).

Where binary search trees are used

An unbalanced binary search tree is mostly a structure for learning on, and the reason is the one demonstrated above: insert keys in sorted order and every node becomes a right child, the tree degenerates into a linked list, and every operation falls back to O(n). Sorted input is not an exotic case — ids, timestamps and alphabetised names all arrive that way — so production code uses a balanced variant. Those variants keep everything on this page (the ordering invariant, the search, the insert, the two deletion cases) and add a rule for keeping the height down.

  • Red-black trees back the ordered maps and sets of the C++, Java and .NET standard libraries, and are used throughout the Linux kernel.
  • AVL trees hold a stricter balance and suit read-heavy indexes; the ZFS filesystem and the illumos kernel use them widely.
  • Splay trees move whatever was just touched to the root, which pays off when the same keys keep coming back — caches and lookup tables with hot spots.
  • B-trees and B+ trees widen each node to a whole disk page, which is why databases and filesystems index with them rather than with binary trees.
  • Treaps and skip lists reach the same expected O(log n) through randomisation rather than rebalancing rules, which makes them simpler to write and easier to make concurrent.

The idea itself — keep ordered data so that search, insert and delete are all cheap — turns up wherever a hash table is not enough because order matters: symbol tables in compilers and interpreters, in-memory indexes, ordered sets in language runtimes, and any query of the form "everything between these two keys", which a hash table cannot answer at all.

See Catalan Numbers for why there are 5 differently shaped binary trees with 3 nodes (and 14 with 4).

A KD-tree is a binary search tree that compares x and y in turn; see KD-tree vs R-tree.

For range sums instead of key lookups, see the segment tree.

A treap keeps a BST shallow by giving each node a random priority and rotating by it.

In a general rooted tree (no keys to compare) the lowest common ancestor needs a method like binary lifting.

What the page leaves out

The page stores small integer keys only, with no values attached to them, and a key equal to one already there simply goes into the right subtree. Real ordered maps keep a value with every key, decide what to do with duplicates, and often store parent pointers or keep iterators valid during changes. The page also never rebalances: see AVL trees and red-black trees for that. It leaves out range queries, finding the k-th smallest key, and how a tree is laid out in memory.