Binary Search Trees & the Release Catalog
Tunebox's catalog filter answers "everything released from 1990 to 2005". A sorted list answers that fast — but new releases land every day, and each one slotted into the middle of a list shifts everything after it. A binary search tree keeps the catalog in order and takes a new release by walking a single path.
The BST property
A binary search tree is a binary tree with one rule, holding at every node: every key in the left subtree is smaller, and every key in the right subtree is bigger. Plenty of Tunebox releases share a year, so we settle ties by sending equal keys right.
1999
/ \
1987 2012
\ /
1994 2005The rule covers whole subtrees, not just a node's two children — and that's exactly where a quick check goes wrong:
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def looks_ok(node):
if node is None:
return True
if node.left and node.left.key >= node.key:
return False
if node.right and node.right.key < node.key:
return False
return looks_ok(node.left) and looks_ok(node.right)
root = Node(1999, Node(1987, None, Node(2003)), Node(2012))
print(looks_ok(root))Search in O(h)
The rule turns search into one path. Compare with the node, then discard a whole subtree:
Every step drops one level, so search costs O(h), where h is the tree's height.
Insert: search until you fall off, then attach
Insertion follows the path a search would. When it steps onto None, that empty
slot is where the new key belongs. Step through four inserts:
Returning root from every call is what lets one line — root.left = insert(...) —
attach the new node, and it handles an empty tree for free.
In-order traversal gives sorted order
An in-order walk visits the left subtree (all smaller), then the node, then the right subtree (all bigger). On a BST, that is sorted order. Equal keys come out in the order they were added, because each later one went right.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.key)
inorder(node.right, out)
return out
root = None
for year in [2001, 1995, 2010, 1990, 1998]:
root = insert(root, year)
print(inorder(root, []))❓ Cross-question — "So inserting everything and walking in-order is a sort?" Yes — it's called tree sort. It's O(n log n) while the tree stays bushy and O(n²) when it doesn't, which is the next part.
Balanced vs degenerate: insertion order matters
Every operation so far is O(h). The same seven years can build a tree of height 3 or height 7, and only the order they arrive in decides which:
A catalog imported oldest-first is already sorted, so a plain BST becomes a chain and every "fast" O(h) operation is really O(n). Self-balancing trees prevent that by reshaping themselves with small rotations after each insert or delete. AVL trees keep the heights of every node's two subtrees within 1 of each other; red-black trees colour their nodes so that no root-to-leaf path is more than twice as long as any other. Both guarantee h = O(log n). You won't implement them here — knowing they exist, and why, is the point.
Coming from Java/JS: Java's
TreeMapandTreeSetare red-black trees, and so, in practice, is C++'sstd::map. Python's standard library has no balanced tree; its usual answer is a sorted list withbisect(below). JavaScript has neither built in.
Range queries: prune what can't match
For "released from start to end", walk in-order but skip any subtree that can't
hold an answer. This version prunes in the wrong directions:
This should print the three years from 1990 to 2005, in order. It prints only [1999], because it skips subtrees that hold answers.
Fixed, the walk follows one path down each edge of the range and then touches only
the m keys it returns: O(h + m).
| Operation | BST, balanced | BST, degenerate | Sorted list + bisect |
|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) |
| Insert | O(log n) | O(n) | O(n) — items shift |
| Every key in order | O(n) | O(n) | O(n) |
Range with m results |
O(log n + m) | O(n) | O(log n + m) |
Idioms & real-world patterns
A sorted list and bisect: Python's everyday answer
For a catalog that's read far more often than it changes, a sorted list is simpler
and, in practice, fast. bisect_left and bisect_right find the edges of a range in
O(log n):
Databases take the tree idea further: their indexes are B-trees, whose nodes each hold hundreds of keys, so even a billion-row index is only a few levels deep.
⚡ Advanced — deleting a key
Deletion has three cases. A leaf simply goes. A node with one child is replaced by that child. A node with two children takes the key of its in-order successor — the smallest key in its right subtree — and that successor, which has no left child, is then deleted from the right subtree. Each case keeps the BST property, and each costs O(h).
⚡ Advanced — floor and ceiling
"The latest release on or before 2000" is the floor of 2000. Walk down: when a node's key is ≤ the target it's a candidate, so remember it and look right for a closer one; otherwise go left. One path, O(h) — the same pruning as a range query.
🎯 Your turn
Write releases_between(releases, start, end). releases is a list of [year, title]
pairs. Insert them into a BST keyed by year, in the order given, with ties going
right. Return the titles released from start to end inclusive, in year order;
same-year titles keep the order they were added:
releases_between([[1999, "Midnight"], [1987, "Neon"], [2012, "Tides"], [1994, "Glass"], [2005, "Static"]], 1990, 2005)→["Glass", "Midnight", "Static"]releases_between([], 1900, 2100)→[]
Hint — insert every pair first, then run the pruned in-order walk — once you've fixed it.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅