A binary search tree (BST) is a binary tree in which each node's key is greater than all keys in its left subtree and less than all keys in its right subtree — providing O(log n) average-case search, insert, and delete, and O(n) in-order traversal that yields a sorted sequence.
A binary search tree organises values so that every node's left subtree contains only smaller values and its right subtree contains only larger values — letting you find any value by halving the search space at every node.
The BST property
For every node x: all keys in x's left subtree are < x.key, and all keys in x's right subtree are > x.key. This invariant means: to find a key k, start at the root. If k = root, found. If k < root, go left. If k > root, go right. Repeat until found or null. At each step you eliminate half the remaining tree — O(log n) in a balanced tree.
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
class BST:
def __init__(self): self.root = None
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if node is None: return Node(key)
if key < node.key: node.left = self._insert(node.left, key)
elif key > node.key: node.right = self._insert(node.right, key)
return node # duplicate keys ignored
def search(self, key):
node = self.root
while node:
if key == node.key: return True
elif key < node.key: node = node.left
else: node = node.right
return False
def inorder(self): # sorted traversal — O(n)
result = []
def _in(n):
if n: _in(n.left); result.append(n.key); _in(n.right)
_in(self.root)
return result
bst = BST()
for k in [5, 3, 8, 1, 4, 7, 9]:
bst.insert(k)
print(bst.search(4)) # True
print(bst.inorder()) # [1, 3, 4, 5, 7, 8, 9] — sorted!Complexity
| Case | Time | Space | Notes |
|---|---|---|---|
| Search | O(log n) avg | O(n) worst | Worst case: degenerate tree (sorted input) |
| Insert | O(log n) avg | O(n) worst | Same as search |
| Delete | O(log n) avg | O(n) worst | Same as search |
| In-order traversal | O(n) | O(n) | Yields sorted output |
| Space | O(n) | O(n) | Pointer overhead per node |
Average assumes random insertion order. Worst case when inserted in sorted or reverse-sorted order.
In-order traversal gives sorted output
In-order traversal (left, root, right) visits every node in sorted order. This is the key connection between BSTs and sorting: inserting n elements into a BST and traversing in order is equivalent to sorting — both O(n log n) average. This is also why BSTs are useful for maintaining a dynamic sorted set with O(log n) search, insert, and delete.
The degenerate case: why balance matters
Inserting elements in sorted order (1, 2, 3, … n) into a BST creates a degenerate tree — a linked list leaning right. Every node has an empty left subtree and one right child. Height = n. Search, insert, and delete all become O(n). The BST property is maintained, but the tree provides no speedup over a linked list. This is why balanced BSTs are used in practice.
Self-balancing BSTs
AVL trees (Adelson-Velsky & Landis, 1962): maintain the invariant that the heights of every node's left and right subtrees differ by at most 1. On insert or delete, one or two rotations restore balance. Guaranteed height O(log n). Red-Black trees (Bayer, 1972; extended by Guibas & Sedgewick, 1978): each node is coloured red or black; five invariants ensure height ≤ 2 log₂(n+1). Fewer rotations than AVL on insert/delete. Java's TreeMap and TreeSet, C++ std::map and std::set, and Linux kernel's rbtree use Red-Black trees.
BST deletion: the successor case
Deleting a node with two children: replace the node's key with its in-order successor (the smallest key in the right subtree — the leftmost node of the right subtree), then delete the successor from the right subtree. The successor has at most one child (no left child), so its deletion is simpler. This maintains the BST property throughout.
def _min_node(node):
while node.left: node = node.left
return node
def _delete(node, key):
if node is None: return None
if key < node.key: node.left = _delete(node.left, key)
elif key > node.key: node.right = _delete(node.right, key)
else:
if node.left is None: return node.right # 0 or 1 child
if node.right is None: return node.left
# 2 children: replace with in-order successor
succ = _min_node(node.right)
node.key = succ.key
node.right = _delete(node.right, succ.key)
return nodeAVL rotations and the balance invariant
An AVL tree maintains balance factor bf(x) = height(left) − height(right) ∈ {−1, 0, 1} for every node. On insertion, at most one or two rotations suffice to restore balance. The four rotation cases: left-left (single right rotation), right-right (single left rotation), left-right (double rotation), right-left (double rotation). The height of an AVL tree with n nodes is at most 1.44 log₂(n+2) − 0.328 — provably O(log n).
Red-Black trees: invariants and proof
Five Red-Black invariants (CLRS §13.1): (1) every node is red or black; (2) root is black; (3) leaves (NIL) are black; (4) a red node's children are both black; (5) all paths from a node to its descendant leaves have the same number of black nodes (black height). Consequence: the height of a Red-Black tree with n nodes is at most 2 log₂(n+1). The 2× factor vs. AVL is why Red-Black trees have O(log n) but a slightly larger constant than AVL.
Cormen, T. H. et al. (2022). CLRS (4th ed.), Ch.12 — BSTs; Ch.13 — Red-Black trees. Adelson-Velsky, G. M. & Landis, E. M. (1962). "An algorithm for the organisation of information." Doklady Akademii Nauk SSSR 146(2). Guibas, L. J. & Sedgewick, R. (1978). "A dichromatic framework for balanced trees." FOCS '78.