The problem it solves
A binary search tree keeps its values in sorted order by position. At every node: the entire left subtree is smaller, the entire right subtree is larger. Searching then works exactly like binary search — compare, discard half, repeat.
Search, Insert, Delete
Searching is a walk: compare with the current node, go left if smaller, right if larger, stop when equal or when you fall off the tree. Insertion follows the same walk and attaches the new node where the search failed.
Deletion is the fiddly one, with three cases:
- Leaf — just remove it.
- One child — the child takes its place.
- Two children — replace the value with its in-order successor (the smallest value in the right subtree), then delete that successor. Only this choice preserves the BST rule.
In-Order Traversal Sorts For Free
Visit left subtree, then the node, then the right subtree. Because of the BST rule, this emits every value in ascending sorted order — press In and read the output.
The other two orders have their own uses: pre-order (node first) is how you copy or serialise a tree, and post-order (node last) is how you delete one safely, since children are freed before their parent.
The Fatal Weakness
Press Sorted input. Inserting already-sorted values means every new value is larger than everything before it, so it always goes right. The tree becomes a single downward chain — a linked list wearing a tree costume.
Height goes from O(log n) to O(n), and every operation degrades with it. This is not a rare edge case: inserting sorted data is extremely common in practice.
Which Is Why Self-Balancing Trees Exist
AVL trees and red-black trees detect when a subtree grows lopsided and perform rotations to restore balance, guaranteeing O(log n) regardless of insertion order. Red-black trees are what back std::map in C++ and TreeMap in Java.
Compare the height readout after pressing Balanced versus Sorted input with the same values — the gap is exactly what balancing buys.
BST or Hash Table?
A hash table is faster for pure lookup — O(1) versus O(log n). But a BST keeps its data ordered, which a hash table cannot. Use a tree when you need sorted iteration, range queries ("all values between 20 and 50"), or nearest-neighbour lookups. Use a hash table when you only ever ask "is this exact key present?".
Ordered structure, not just storage
A binary search tree keeps one invariant at every node:
Everything in the left subtree is smaller; everything in the right subtree is larger.
That single rule makes search work like binary search: compare, then discard half the tree.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Searching for 6: 6 < 8 so go left; 6 > 3 so go right; found. Three comparisons for seven nodes.
| Operation | Balanced | Degenerate |
|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| In-order traversal | O(n) | O(n) |
| Minimum / maximum | O(log n) | O(n) |
The difference between those columns is the whole subject, and it is what balanced trees exist to guarantee.
Why an in-order traversal is sorted
Visit the left subtree, then the node, then the right subtree, and values come out in ascending order — because everything left is smaller and everything right is larger, recursively.
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.value)
inorder(node.right, out)
That is the property hash tables cannot offer, and it is why BSTs are used where ordering matters:
- Range queries — all values between 10 and 50, found by traversing a subtree.
- Nearest neighbour — the closest value to a target.
- Sorted iteration without sorting.
- Successor and predecessor of a given value.
- Minimum and maximum — walk left or right to the end.
A hash table does none of those. That is the trade: O(1) unordered lookup, or O(log n) with order.
The degenerate case
Insert 1, 2, 3, 4, 5 into an empty BST in that order and every node becomes the right child of the last. The tree is a linked list, and every operation is O(n).
Sorted input produces the worst possible tree. That is not a rare pathological case — inserting records in id order, or in date order, is entirely normal.
Three responses:
Self-balancing trees. AVL and red-black trees rotate on insertion to keep the height O(log n) automatically. This is what production implementations use.
Randomised insertion order, if you control it. Expected height O(log n).
A different structure. A sorted array with binary search, or a skip list, or a B-tree for disk-based data.
| Tree | Balance rule | Character |
|---|
| AVL | Heights differ by at most 1 | Strictly balanced; faster lookups |
| Red-black | Colour rules bound the height | Fewer rotations; faster insertion |
| B-tree | Many keys per node | Designed for disk pages |
| Treap | Random priorities | Simple, probabilistic balance |
Red-black trees are what most standard libraries use for ordered maps — C++'s std::map, Java's TreeMap — because they balance insertion and lookup cost well.
The fatal weakness, measured
A BST gives O(log n) search when it is balanced and O(n) when it is not, and nothing in the plain insert algorithm prevents the second. The gap between those two is the whole reason self-balancing trees exist, and it opens up on the most ordinary input there is.
Guided tour
- Insert a few values and watch each one walk down the tree, going left or right at every comparison.
- Search for something. The highlighted path shows roughly half the remaining tree being discarded at each step.
- Press In-order traversal. The values come out perfectly sorted — that is the BST rule paying off.
- Press Sorted input. The tree collapses into a straight line and the height jumps to n — every search is now linear.
- Delete a node with two children and note which value replaces it: the in-order successor, the only choice that keeps the ordering intact.
In one line
A BST turns the binary-search idea into a living structure with O(log n) search, insert and delete — but only while it stays bushy. Sorted input degenerates it to a linked list, which is precisely why self-balancing variants exist and why they, not plain BSTs, are what production libraries ship.
Deletion, the awkward operation
Insertion and search are straightforward. Deletion has three cases, and the third is where implementations go wrong.
A leaf. Remove it.
One child. Replace the node with its child.
Two children. Replace the node's value with its in-order successor — the smallest value in its right subtree — then delete that successor, which by construction has at most one child.
def delete(node, value):
if not node:
return None
if value < node.value:
node.left = delete(node.left, value)
elif value > node.value:
node.right = delete(node.right, value)
else:
if not node.left:
return node.right
if not node.right:
return node.left
succ = node.right # find the in-order successor
while succ.left:
succ = succ.left
node.value = succ.value
node.right = delete(node.right, succ.value)
return node
The predecessor (largest in the left subtree) works equally well. Either choice preserves the ordering invariant, which is what matters.
Note that repeated deletions can unbalance a tree even if insertions were balanced — another argument for a self-balancing implementation.
Where trees beat hash tables
| Need | Structure |
|---|
| Lookup by exact key | Hash table — O(1) |
| Range queries | Tree |
| Sorted iteration | Tree |
| Nearest key | Tree |
| Minimum or maximum | Tree, or a heap |
| Predictable worst case | Balanced tree — O(log n) guaranteed |
The last row is worth noting: a hash table's O(1) is an average, with an O(n) worst case; a balanced tree's O(log n) is a guarantee. For latency-sensitive systems that certainty sometimes wins.
In Python specifically, there is no built-in balanced tree. The practical alternatives are dict for unordered lookup, bisect on a sorted list for range queries when insertions are rare, and the third-party sortedcontainers package, which provides sorted list, dict and set types with excellent constant factors.
B-trees, and why databases use them
A B-tree node holds many keys — hundreds — rather than one, so the tree is very shallow: a few levels for millions of records.
The reason is disk. Reading from disk or SSD happens in pages of several kilobytes, and the cost is dominated by the number of page reads rather than the comparisons within a page. A binary tree with a million nodes is 20 levels deep, meaning up to 20 page reads. A B-tree with 200 keys per node is 3 levels deep — 3 reads.
That is why every relational database index is a B-tree (usually a B+ tree, with all values in the leaves and the leaves linked for range scans). It is the same ordering invariant, restructured around the hardware.
Questions people ask
Why not always use a hash table? Because it has no order. Range queries, sorted iteration and nearest-key lookups all need a tree.
What makes a tree balanced? Height O(log n). AVL and red-black trees enforce it with rotations on insertion and deletion.
What happens with sorted insertions? An unbalanced tree degrades to a linked list — O(n) operations. This is common in practice, not a corner case.
How do I do a range query? Traverse in order, pruning subtrees entirely outside the range.
Does Python have a balanced tree? Not in the standard library. Use bisect on a sorted list, or sortedcontainers.
What is the difference between a BST and a heap? A BST orders left-node-right for sorted access; a heap only orders parent against children, giving O(1) access to the extreme value and no ordering otherwise.
Recap in one screen
- Left subtree smaller, right subtree larger — that invariant gives O(log n) search on a balanced tree.
- An in-order traversal yields sorted values, which is what hash tables cannot do.
- Sorted insertions produce a degenerate O(n) tree, so self-balancing (AVL, red-black) is what production uses.
- Deletion with two children replaces the node with its in-order successor.
- B-trees widen the nodes to match disk pages, which is why every database index is one.