What you'll learn
A plain binary tree has no rules about where values go. A binary search tree (BST) adds one simple rule that turns the tree into a searchable, always-sorted structure — one that finds, inserts, and removes values in O(log n) time when it stays balanced.
By the end you'll be able to:
- State the BST property and why it enables fast search
- Insert and search by walking left or right at each node
- Delete a node in all three cases, including the two-child case
- Explain why an unbalanced BST degrades to a linked list
The BST property
A binary search tree is a binary tree where, for every node:
- every value in its left subtree is less than the node's value, and
- every value in its right subtree is greater.
That single invariant means the tree is sorted: an in-order traversal (left, node, right) visits the values in ascending order. And it tells you exactly where to look — at each node you can throw away half the remaining tree, just like binary search.
Key idea
Insertion
To insert a value, start at the root and compare. Go left if it's smaller, right if it's larger, and repeat until you fall off the tree — that empty spot is exactly where the new leaf belongs. Press Play to build a BST from the sequence 50, 30, 70, 20, 40, 60, 80, or step through one comparison at a time.
The code mirrors the animation exactly — a tiny recursive walk that returns the (possibly new) subtree:
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):
self.root = self._insert(self.root, value)
def _insert(self, node, value):
if node is None: # empty spot: create the node
return Node(value)
if value < node.value:
node.left = self._insert(node.left, value)
elif value > node.value:
node.right = self._insert(node.right, value)
return node # duplicates ignoredSearching
Search is the same walk without the insert: compare, go left or right, and stop when you match — or when you run off the tree. Watch a hit (find 60) and a miss (look for 25):
def search(self, value):
node = self.root
while node is not None:
if value == node.value:
return True # found
node = node.left if value < node.value else node.right
return False # ran off the treeNote
log₂(n) in a balanced tree.Deletion
Deletion is the one tricky operation, because removing a node must keep the BST property intact. There are three cases:
| Case | The node to delete has… | What to do |
|---|---|---|
Leaf | no children | Just remove it. |
One child | a left or a right child | Replace the node with that child. |
Two children | both a left and a right child | Copy its in-order successor (smallest value in the right subtree), then delete that successor. |
The two-child case is the clever one: the in-order successor is the next-largest value, so putting it in the deleted node's place preserves order. It always has at most one child, so deleting it falls back to one of the easy cases.
def _delete(self, node, value):
if node is None:
return None
if value < node.value:
node.left = self._delete(node.left, value)
elif value > node.value:
node.right = self._delete(node.right, value)
else:
# found the node to delete
if node.left is None: return node.right # 0 or 1 child
if node.right is None: return node.left
# 2 children: copy the in-order successor, then delete it
succ = node.right
while succ.left:
succ = succ.left
node.value = succ.value
node.right = self._delete(node.right, succ.value)
return nodeWhy balance matters
Every operation costs O(height). If you insert values in a nice mixed order, the height stays near log₂(n) and everything is fast. But insert values in sorted order — 10, 20, 30, 40, … — and each new node hangs off the right, producing a tree that is really just a linked list with height n. Search degrades from O(log n) to O(n).
Watch out
O(log n) height no matter the input.Complexity
| Operation | Balanced (average) | Unbalanced (worst) |
|---|---|---|
search | O(log n) | O(n) |
insert | O(log n) | O(n) |
delete | O(log n) | O(n) |
| Space | O(n) | O(n) |
Recap & quick check
Key takeaways
- BST property: left subtree < node < right subtree, for every node.
- Insert and search walk down one child per level, discarding the other subtree each time.
- In-order traversal of a BST yields the values in sorted order.
- Deletion has three cases; the two-child case copies the in-order successor, then deletes it.
- Cost is O(height): balanced ≈ O(log n), but a bad insertion order can degrade it to O(n).
Quick check
1. In a BST, where do values smaller than a node live?
2. An in-order traversal of a BST produces values in what order?
3. Deleting a node with two children uses which value to replace it?
4. What makes a BST degrade to O(n) operations?
The BST is fast when balanced. Next we guarantee that balance. Next up: Module 18 — AVL Trees, where rotations keep the height in check automatically.