Binary Search Trees — Search, Insert, and Delete in O(log n)
bst-operations not found in registry.What Is a Binary Search Tree?
A binary search tree (BST) is a binary tree with one rule: for every node, everything in its left subtree is smaller and everything in its right subtree is larger.
Think of it like a game of higher or lower. Someone picks a number, and at each guess you eliminate half the remaining possibilities. A BST does exactly this — each comparison cuts the search space in half.
This gives you O(log n) search, insert, and delete when the tree is balanced.
The BST Property
The BST invariant: for any node with value x, every node in the left subtree holds a value less than x, and every node in the right subtree holds a value greater than x.
This applies to all descendants, not just immediate children.
Inorder Traversal Gives Sorted Output
Visit nodes in left → root → right order and you get every value in sorted order.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, value):
if self.root is None:
self.root = Node(value)
else:
self._insert(self.root, value)
def _insert(self, node, value):
if value < node.value:
if node.left is None:
node.left = Node(value)
else:
self._insert(node.left, value)
else:
if node.right is None:
node.right = Node(value)
else:
self._insert(node.right, value)
def search(self, value):
return self._search(self.root, value)
def _search(self, node, value):
if node is None:
return False
if value == node.value:
return True
elif value < node.value:
return self._search(node.left, value)
else:
return self._search(node.right, value)
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.value)
self._inorder(node.right, result)
tree = BST()
for val in [50, 30, 70, 20, 40, 60, 80]:
tree.insert(val)
print("Inorder (sorted):", tree.inorder())
print("Search 40:", tree.search(40))
print("Search 99:", tree.search(99))| Operation | Best | Average | Worst | Space |
|---|---|---|---|---|
| Search | O(1) | O(log n) | O(n) | O(h) |
| Insert | O(1) | O(log n) | O(n) | O(h) |
| Delete | O(log n) | O(log n) | O(n) | O(h) |
| Inorder | O(n) | O(n) | O(n) | O(h) |
Key Takeaways
- The BST invariant enables O(log n) search, insert, and delete when balanced.
- Worst case is O(n) when the tree degenerates into a linked list.
- Inorder traversal always produces sorted output.
- Self-balancing trees (AVL, Red-Black) guarantee O(log n) height.
- BSTs power TreeMap in Java, std::map in C++, and many database indexes.