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

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 a binary search tree: the path compared from the root down

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 a key into a binary search tree as a new 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 a leaf from a binary search tree

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 a node with one child: the child takes its place

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 is always a leaf node, and can be found by starting at the left subtree’s root and moving right. We can then swap the node being removed with its IOP and delete it, as it is now a leaf.

Removing 4, which has two children: swap it with its in-order predecessor 3, then delete it as 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

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

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.