A binary search tree (BST) is a binary tree where every node's left subtree contains smaller keys and right subtree contains larger keys. Average O(log n) operations on random input — but a plain BST is unbalanced and degrades to O(n) on sorted input.
The BST ordering rule is what makes the structure useful: it turns a tree into a sorted collection that supports search, insertion, deletion, predecessor and successor queries, range scans, and in-order iteration with a single descent per operation. Balanced variants such as AVL trees, red-black trees, and B-trees keep that rule and add constraints on shape so the descent stays logarithmic.
Each comparison discards an entire subtree. In the tree above, the left subtree of 5 holds only keys smaller than 5, so once the search learns that 7 is larger it never looks at 1, 3, or 4. The number of comparisons equals the depth of the target plus one, so search cost is proportional to the height of the tree. For this perfectly balanced seven-node tree the height is 2, the minimum possible: floor(log2 7).
The tree's shape is decided entirely by insertion order. Inserting keys in random order produces an expected height of about 2.99 log2 n in the limit, which is O(log n). Inserting them already sorted makes every new key the right child of the previous one, so the "tree" is a chain and all operations become linear. Real data is often partly sorted (timestamps, auto-increment ids), which is why self-balancing trees are used in practice.
| Average | Worst | Space | ||||||
|---|---|---|---|---|---|---|---|---|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Worst |
Θ(log n) |
Θ(log n) |
Θ(log n) |
Θ(log n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
Search: start at the root; go left if the target is smaller, right if larger, until you find it or hit None. Insert: same descent, then attach the new node where None was. Delete: three cases — leaf (just remove), one child (splice), two children (replace with in-order successor and recurse).
class Node:
__slots__ = ("key", "left", "right")
def __init__(self, key):
self.key, self.left, self.right = key, None, None
class BST:
def __init__(self):
self.root = None
def insert(self, key): # avg O(log n), worst O(n)
def _ins(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = _ins(node.left, key)
elif key > node.key:
node.right = _ins(node.right, key)
return node
self.root = _ins(self.root, key)
def contains(self, key): # avg O(log n), worst O(n)
node = self.root
while node:
if key == node.key: return True
node = node.left if key < node.key else node.right
return False
def in_order(self):
out = []
def _walk(n):
if n is None: return
_walk(n.left); out.append(n.key); _walk(n.right)
_walk(self.root)
return out
bst = BST()
for k in [5, 3, 8, 1, 4, 7, 9]:
bst.insert(k)
print(bst.in_order()) # [1, 3, 4, 5, 7, 8, 9]
print(bst.contains(7)) # Truesortedcontainers.SortedList in Python gives you ordered set/dict semantics without the implementation cost.Deletion is the only operation with real case analysis. A leaf is removed directly; a node with one child is replaced by that child; a node with two children takes the key of its in-order successor (the minimum of its right subtree), and then that successor, which has at most one child, is deleted from the right subtree. The functions below extend the class above.
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 # leaf or right child only
if node.right is None:
return node.left # left child only
succ = node.right # two children: find successor
while succ.left:
succ = succ.left
node.key = succ.key
node.right = delete(node.right, succ.key)
return node
def range_query(node, lo, hi, out):
"""Append keys in [lo, hi] in sorted order, skipping subtrees outside the range."""
if node is None:
return out
if lo < node.key:
range_query(node.left, lo, hi, out)
if lo <= node.key <= hi:
out.append(node.key)
if node.key < hi:
range_query(node.right, lo, hi, out)
return out
bst.root = delete(bst.root, 5) # root has two children; successor 7 moves up
print(bst.in_order()) # [1, 3, 4, 7, 8, 9]
print(range_query(bst.root, 3, 8, [])) # [3, 4, 7, 8]The range query shows what a hash table cannot do. It visits only nodes on the boundary paths plus the k keys reported, costing O(h + k) for height h. That is the reason ordered indexes in databases are trees (B-trees and B+ trees) rather than hashes.
When to use a BST. Use a balanced BST, or a library that provides one, when you need sorted iteration, nearest-key lookups (floor and ceiling), or range scans alongside inserts and deletes. Use a hash table when you only need exact-key lookups. Use a sorted array with bisect when the data is mostly static, since it is more compact and cache friendly.