What is a Binary Search Tree
A binary search tree is a binary tree with one rule added: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger.
That is the whole difference from the previous article, and it is the difference between a shape and a search structure. The rule turns the two children from "the left one" and "the right one" into an instruction: compare, then go one way. Every comparison discards an entire subtree.
Looking up a word in a paper dictionary, nobody starts at page one. You open somewhere near the middle, read the word at the top, and that one word tells you which half to throw away. Then you do it again in the half that is left.
You never needed an index, and you never had to look at the words you skipped. All you needed was for the pages to be in order, plus the ability to look at one and compare. A binary search tree is that arrangement built out of nodes: one comparison per node, half the remaining data discarded each time.
every value under 50's left is below 50, every value under its right is above
The problem a Binary Tree couldn't solve
The previous article ended on a specific complaint. A binary tree constrains where nodes can be — full, complete, perfect — but says nothing about which value goes where. So finding a value meant checking every node, O(n), in the best shape and the worst. The shape was predictable and the contents were not.
Compare the two directly. In a plain binary tree, arriving at a node that is not the value you want tells you nothing: the value could be in either subtree, so you have to try both. In a search tree, the same failed comparison tells you exactly which subtree cannot possibly contain it, and you never look there again.
That single bit of information per node is what turns O(n) into . And because the previous article established that a tidy binary tree has height log₂ n, that is O(log n) — 20 comparisons in a million nodes.
The invariant
The rule is worth stating carefully, because the careless version is subtly wrong and the mistake is extremely common.
For every node: every value in the left subtree is less than the node, and every value in the right subtree is greater than it.
The load-bearing word is every.
It is recursive, not local
The tempting shortcut is to check each node against its two children — left child smaller, right child larger — and call it a day. That check accepts trees that are not search trees at all.
60 is 30's right child, so it is larger than its parent — and it sits in 50's left subtree while being larger than 50
Look at 60. Against its parent it is perfectly legal: it is 30's right child and 60 > 30. But it lives in the left subtree of 50, and 60 > 50, which breaks the rule. Search for 60 in that tree and you will go right at the root, into the subtree that does not contain it, and report it missing.
The correct check carries bounds down the tree: a node in the left subtree of 50 must be less than 50, and if it is also in the right subtree of 30 it must be greater than 30. Each step narrows the window.
Reading it left to right gives sorted order
One consequence of the invariant is worth naming because it is what makes a BST more than a lookup table. Take a node's left subtree, then the node, then its right subtree — and the values come out in ascending order. Every time, for any BST.
That falls straight out of the rule: everything left of a node is smaller and everything right is larger, so visiting in that order visits smaller before larger, all the way down. The name for reading a tree that way is in-order, and this article needs nothing more from it than the fact.
This is the promise the hash tables article left open. A hash table implements the Map ADT and is faster on average, but it scatters keys deliberately and so cannot answer "give me these in order" or "give me everything between two values" at all. A BST answers both, and this property is why. It is also visible in the playground below, which prints the tree's values read that way.
Searching, and why it halves
Search is the operation the structure exists for, and it is four lines of logic: compare, and recurse into one side.
40 < 50 so go left · 40 > 30 so go right · found — 60, 70, 80 and 20 were never looked at
Four of the seven nodes were never examined, and that is with a tiny tree. The proportion is what matters: each comparison eliminates a subtree, so the number of nodes you examine is the number of levels, not the number of nodes.
A failed search is just as informative. Walking down and falling off the bottom means the value is not there — and, usefully, the place you fell off is exactly where the value would have to go. Insert is built on that.
Inserting
To insert, search for the value. If you find it, there is nothing to do. If you fall off the bottom, attach a new leaf where you fell.
That is the whole algorithm, and it explains why a BST's shape depends on insertion order: each new value takes the only slot its comparisons allow, and nothing ever moves an existing node. The tree remembers the order it was built in, which is the seed of the problem at the end of this article.
The playground below shows the slot before you commit to it — type a value and the dashed circle is where the comparisons put it.
Deleting — the three cases
Delete is the one operation with real case analysis, because removing a node can leave a hole that its children have to fill legally.
The node is a leaf
Nothing depends on it. Detach it and you are done.
30 keeps its right child and the invariant is untouched
The node has one child
Promote the child. Every value in that child's subtree was already on the correct side of the deleted node's parent, so moving it up one level cannot break anything.
20 was already less than 50, so it is legal as 50's left child
The node has two children
Neither child can simply be promoted — the node has one slot and there are two subtrees to keep. So instead of removing the node, overwrite its value with the next value in sorted order, then delete that value from where it was.
The next value in sorted order is the in-order successor: the smallest value in the right subtree, which you find by going right once and then left as far as possible. It is the right choice because it is larger than everything in the left subtree and smaller than everything else in the right one — exactly the two properties the slot requires.
40 was the smallest value larger than 30, so it satisfies the slot 30 left
And the recursion terminates: the successor is the leftmost node of a subtree, so it has no left child, which means deleting it lands in case one or case two and never case three again.
The operations in Go
Try it yourself
Type a value and watch the dashed slot move as the comparisons place it. Then insert, search and delete — and note the comparison count the status line reports against the tree's height.
insert, search or delete — the path lights up as it walks
When you have a feel for it, press Insert in ascending order and look at what happens. That is the next section.
Common operations and their costs
Every operation here costs the height of the tree, which is the point — and the reason shape matters so much:
| Operation | Balanced tree | Degenerate tree |
|---|---|---|
| Search | ||
| Insert | ||
| Delete | ||
| Minimum, maximum | ||
| All values in order |
Notice there is no O(1) anywhere, and no operation cares about n directly — they all care about h. Everything in this table is the same algorithm in both columns; only the tree's shape differs. Which means the entire performance of a BST rests on a property the structure does not enforce.
Binary Search Trees in the real world
Ordered maps and sets in standard libraries
std::map and std::set in C++, TreeMap and TreeSet in Java. These are the ordered counterparts of the hash-based containers, and they exist for exactly the property this article described: iteration in key order, plus range queries. They are all self-balancing variants rather than plain BSTs, for the reason the next section gives.
Database indexes
Any index that supports WHERE created_at BETWEEN ... AND ... or ORDER BY without a sort is a tree index, because a hash index cannot answer either. Databases use B-trees rather than binary ones — a shape tuned for disk pages — but the ordering property being exploited is this one.
Scheduling and interval problems
"What is the next event after this timestamp" is a BST query: search for the timestamp and take the successor. Anything that needs nearest rather than exact — closest match, next-largest, autocomplete range — wants ordered structure, which rules a hash table out immediately.
Symbol tables where order matters
Compilers and interpreters that need deterministic iteration over declarations use ordered maps, since hash iteration order is arbitrary and, in Go's case, deliberately randomised.
When Binary Search Trees fall short
Sorted input destroys it. This is the big one. Insert 10, 20, 30, 40 in ascending order and every value goes right, because every value is larger than everything already there. The result has height n − 1.
a linked list with an unused Left pointer on every node
And sorted input is not a pathological case someone has to construct — it is the most ordinary thing in the world. Data arrives from an ORDER BY, from a sorted file, from an auto-incrementing id, from a timestamp. The most natural input there is produces the worst possible tree, and every O(log n) in the table above silently becomes O(n).
A hash table is faster when you do not need order. Average O(1) beats O(log n), and by a wider margin than the notation suggests once cache behaviour is counted. Reach for a BST when you need ordered iteration, range queries or nearest-match. If you only ever look values up by exact key, the hash table wins.
Pointer chasing costs more than the comparison count implies. Twenty comparisons in a million-node tree sounds cheap, but each one is a pointer dereference to a node that could be anywhere in the heap — potentially twenty cache misses. This is why the array-backed structures in this series often beat tree-shaped ones in practice at small sizes.
No duplicates, without extra machinery. The invariant uses strict inequalities, so equal values have no legal home. Real implementations either store a count per node or push duplicates consistently to one side, and both complicate delete.
Summary
A binary search tree adds one ordering rule to a binary tree and gets a search structure out of it:
- Left subtree smaller, right subtree larger — for every node — and the rule is recursive, not a check against the parent
- One comparison discards a whole subtree — which is why cost is
O(h), the number of levels, notO(n) - Insert is a failed search plus one leaf — so the tree's shape is a record of the order it was built in
- Delete has three cases — a leaf detaches, one child gets promoted, and two children means overwriting with the in-order successor
- Reading left to right yields sorted order — the property a hash table cannot offer, and the reason ordered maps are tree-backed
- Every cost depends on height, which nothing here guarantees — sorted input gives
n − 1
The key insight is that a BST's performance is a property of its history, not of its definition. Nothing in the structure resists a bad insertion order, and the worst order — sorted — is also the most common one in practice. That is a structure with excellent average behaviour and no floor under its worst case, which for anything holding real data is not a trade you can accept.
The next article puts a floor under it. If the problem is that inserts can make the tree lean, the fix is to notice the lean and undo it — a local rearrangement that preserves the invariant while shortening the tree. That operation is called a rotation, and a handful of them per insert is enough to guarantee O(log n) forever.