Fast lookups that also keep order
A sorted array can be searched very quickly with binary search. But adding a new item means shifting everything after it to make room. A hash table adds and finds items instantly, but keeps them in no order at all, so "what is the next largest?" is a slow question.
A binary search tree aims for both: quick to search, quick to add to, and always in order.
One rule
Each node holds a value and has up to two children, a left one and a right one. The rule, at every node:
Everything in the left subtree is smaller. Everything in the right subtree is larger.
That rule turns every comparison into a decision that discards part of the tree.
Start. An empty tree. The rule for every node: smaller values go somewhere to its left, larger values somewhere to its right.
- Comparisons this step
- 0
- Levels in the tree
- 0
Searching
Start at the root
Compare the value you want with the root's value.
Equal? Found
Stop.
Smaller? Go left. Larger? Go right
The entire other side is ruled out. You never look at it.
Repeat until you find it or run out of tree
Reaching an empty spot means the value is not there.
Inserting works the same way: walk down as if searching, and put the new value in the empty spot where the walk ends.
def search(node, target):
while node is not None:
if target == node.value:
return node
node = node.left if target < node.value else node.right
return NoneIn the demo, finding 60 among seven values took 3 comparisons. With a tree like that, each step down halves what is left.
| Values in a well-shaped tree | Levels to walk |
|---|---|
| 7 | 3 |
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
Reading it in order
Because of the rule, visiting "left subtree, then the node, then right subtree" at every node gives all the values in sorted order. No sorting step is needed: the order is built into the shape. See Depth-First Tree Traversal.
That also makes ordered questions cheap:
- Smallest value: keep going left.
- Largest: keep going right.
- Everything between 30 and 60: walk to 30, then read in order until past 60.
The catch: the shape depends on the order of insertion
Now insert the same seven values in sorted order.
Start. An empty tree. The rule for every node: smaller values go somewhere to its left, larger values somewhere to its right.
- Comparisons this step
- 0
- Levels in the tree
- 0
Every new value is larger than everything before it, so it always goes to the right. The "tree" has one branch. It is a linked list wearing a disguise.
Searching it means walking past every node: 7 comparisons for 7 values, a million for a million. Everything that made the tree fast is gone.
Sorted input is not a rare accident. Data often arrives in order: timestamps, ids that count upwards, an alphabetical list.
Start. An empty tree. The rule for every node: smaller values go somewhere to its left, larger values somewhere to its right.
- Comparisons this step
- 0
- Levels in the tree
- 0
The fix: keep it balanced
A self-balancing tree fixes its own shape as it goes. After each insert or delete it checks whether one side has become too deep, and if so, rearranges a few nodes locally (an operation called a rotation) to even things out. The values and the ordering rule are untouched. Only the shape changes.
Well-known kinds are red-black trees and AVL trees. They guarantee the tree stays about log n levels deep, whatever order the data arrives in.
You rarely write one yourself. They are what sits behind the ordered collections in standard libraries: TreeMap in Java, std::map in C++, and sorted containers in other languages.
When to use one
| You need | Use |
|---|---|
| Lookups by key only | A hash table: simpler and faster |
| Lookups and sorted order, ranges, nearest value | A balanced search tree |
| The smallest item repeatedly | A heap |
| Data that never changes, searched often | A sorted array with binary search |
Key takeaways
- In a binary search tree, smaller values go left of a node and larger values go right.
- Searching follows one path down, discarding the other side at every step.
- A well-shaped tree of a million values is only 20 levels deep.
- Inserting values in sorted order produces a chain, and every operation becomes slow.
- Self-balancing trees rearrange themselves to stay shallow, and are what real libraries use.