"A hash map gives you instant lookup but zero order. A binary search tree gives you both — lookup AND order — by enforcing one simple rule at every single node."
The One Invariant
A binary search tree (BST) is a binary tree with one unbreakable rule: for every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. That invariant holds recursively, at every node, all the way down. From it, everything follows almost for free.
Search: start at the root, compare. Smaller? Go left. Larger? Go right. Each comparison discards an entire subtree, so you halve the search space every step — O(log n) when the tree is balanced. It's literally binary search, made into a living structure. Insert: search for where the key would be, and attach it there as a new leaf. In-order traversal (left-node-right) walks the keys in sorted order, for free — the property from the last lesson.
The Answer to Hashing's Blind Spot
Remember hashing's failure: no order, no range queries. The BST is the structure that fills exactly that gap. It does the things a hash map can't:
min / max — walk all the way left / all the way right: O(log n).
sorted iteration — in-order traversal: O(n), already in order.
range queries — "all keys between 10 and 20" — prune subtrees outside the range.
floor / ceiling — "largest key ≤ x" / "smallest key ≥ x" — fall out of the search path.
This is why "I need fast lookup and order" sends you from a hash map to a tree. They're complementary tools, not competitors.
BST invariant: at every node, left subtree < node < right subtree. That gives O(log n) search/insert/delete when balanced, sorted in-order traversal for free, plus min/max/range/floor/ceiling — exactly the ordered operations a hash map can't do.
The Catch That Sets Up the Next Lesson
All of that O(log n) goodness has a fatal asterisk: it only holds if the tree is balanced. Insert keys in sorted order (1, 2, 3, 4, 5…) into a plain BST and each new key goes right, right, right — the tree degenerates into a one-sided chain that's just a linked list wearing tree clothes. Now search is O(n), and you've lost everything. Since sorted-ish input is extremely common in the real world, this isn't a rare edge case — it's the default failure. Fixing it is what the next lesson, on balancing, is entirely about.
Pippa's Confession
I built a BST, tested it on random data, saw beautiful O(log n), and shipped it proud. Then it ate already-sorted input and turned into a 10,000-deep chain that blew the recursion limit. Dad just nodded: "A plain BST trusts its input to be shuffled. Real input rarely is." That bruise taught me the difference between 'works in the demo' and 'survives production' — and why balanced trees, which I'd dismissed as fussy, exist at all.
Code
BST insert/search, and the sorted-input trap·python
class BSTNode:
def __init__(self, key): self.key = key; self.left = None; self.right = None
def insert(root, key):
if root is None:
return BSTNode(key) # found the empty spot -> attach as leaf
if key < root.key:
root.left = insert(root.left, key) # smaller -> go left
elif key > root.key:
root.right = insert(root.right, key) # larger -> go right
return root
def search(root, key): # O(log n) when balanced
while root:
if key == root.key: return True
root = root.left if key < root.key else root.right # halve each step
return False
def inorder(root): # left, node, right -> SORTED
if root is None: return []
return inorder(root.left) + [root.key] + inorder(root.right)
# Balanced-ish insertion order:
balanced = None
for k in [4, 2, 6, 1, 3, 5, 7]:
balanced = insert(balanced, k)
print("search 5:", search(balanced, 5)) # True
print("sorted :", inorder(balanced)) # [1,2,3,4,5,6,7] — order, for free
# THE TRAP: inserting in sorted order degenerates into a chain.
degenerate = None
for k in [1, 2, 3, 4, 5]:
degenerate = insert(degenerate, k) # each goes right -> a linked list!
# 'degenerate' is now height 4 (O(n) search), not height ~2. Same code, bad input.
Insert the keys 8, 3, 10, 1, 6 into an empty BST, in that order, and draw the resulting shape. Then trace the search for 6: which nodes does it visit? Finally, explain why inserting those same five keys in SORTED order (1, 3, 6, 8, 10) produces a much worse tree, and what its height becomes.
Hint
8 is root; 3 left, 10 right; 1 left-of-3, 6 right-of-3. Search 6: 8 → 3 → 6, three nodes. Sorted insertion makes 1→3→6→8→10 a right-leaning chain of height 4 — a linked list, O(n) search.
Progress
Progress is local-only — sign in to sync across devices.