Intuition First: Twenty Questions#
A binary search tree plays Twenty Questions with your data. At every node you ask one yes/no question ("is the value I'm after smaller than this one?"), and the answer lets you discard an entire half of what's left to check. Smaller things always live down the left branch, bigger things down the right, so each step zooms you in.
It's the dictionary-flip of binary search, but baked permanently into the shape of the structure. Follow that one rule down from the top and you pinpoint any value in roughly log(n) questions. It's the same reason 20 yes/no questions can pin down any of a million possibilities.
The Concept#
A binary search tree (BST) is a binary tree with one extra rule, the BST invariant.
For every node N, every key in N's left subtree is strictly less than N's key, and every key in N's right subtree is strictly greater than N's key.
This rule holds at every level and for every ancestor, as well as between a node and its immediate children. The key 5 at the root of a subtree means every key to its left is below 5 and every key to its right is above 5, no matter how deep the tree goes.
The payoff is immediate: in-order traversal (left → node → right) visits every key in ascending sorted order. A BST is really a sorted list disguised as a tree.
Core Operations#
Search and Insert: O(h)#
Both operations walk down the tree making binary decisions at each step. At the current node, compare the target key:
- If equal, you've found it (search) or detected a duplicate (insert).
- If smaller, go left.
- If larger, go right.
Because each comparison eliminates an entire subtree, you descend at most h levels, where h is the height of the tree. For a balanced tree, h ≈ log₂ n; for a completely skewed tree (keys inserted in sorted order), h = n.
Validate a BST: O(n)#
Checking each node only against its immediate parent is not sufficient. Consider a node with key 3 that is the right child of 1 and the left child of 10. Locally it looks fine, but if it were the left child of 5 it would violate the invariant two levels up.
The correct approach passes a range (low, high) down the recursion. At the root the range is (-∞, +∞). When you recurse left, the upper bound tightens to the current node's key. When you recurse right, the lower bound tightens. A node is invalid the moment its key falls outside the range it inherited.
Lowest Common Ancestor: O(h)#
Given two target keys p and q, the LCA is the deepest node that is an ancestor of both. In a BST this is particularly clean: walk down from the root. If both p and q are less than the current node, the LCA is in the left subtree. If both are greater, it's in the right subtree. The moment they split to different sides, or one of them equals the current node, you've found the LCA.
Kth Smallest: O(h + k)#
In-order traversal yields keys in sorted order, so the kth smallest is simply the kth node visited in an in-order walk. Implement this as a recursive descent that counts visited nodes; once the counter reaches k, record the answer and return.
Code Implementation#
Complexity Analysis#
| Operation | Time | Space | Notes |
|---|---|---|---|
| search | O(h) | O(1) iterative | O(h) stack if recursive |
| insert | O(h) | O(h) | recursion depth |
| validate | O(n) | O(h) | recursion depth |
| LCA | O(h) | O(h) | recursion depth |
| kth smallest | O(h + k) | O(h) | in-order walk |
For a balanced tree, h = O(log n) and all operations are logarithmic. For a skewed tree (e.g., keys inserted in sorted ascending order), h = O(n) and all operations degrade to linear. This motivates self-balancing trees (AVL, Red-Black), but those are a separate topic.
Interactive Lab#
Every visualization below runs on the same seven-key tree: 20 at the root, 10 and 30 beneath it, and 5, 15, 25, 35 as the four leaves. It is perfectly balanced, so h = 2 and no operation ever takes more than three comparisons. Keep the sorted order (5, 10, 15, 20, 25, 30, 35) in mind; it is what every one of these operations is secretly exploiting.
Let's take the example of searching for 15. Watch the comparison at each node and, more importantly, watch what gets skipped: 15 < 20 throws away 30 and both of its children in one step, then 15 > 10 throws away 5. Three nodes examined out of seven.
Now the same descent, but with 22 looking for a home rather than a match. 22 > 20 sends it right, 22 < 30 sends it left, 22 < 25 sends it left again, into an empty slot, which is where it lands. Insert is search that keeps going until it runs out of tree.
Validation walks the whole tree instead, carrying a (low, high) range that tightens on the way down: going left drops the upper bound to the current key, going right lifts the lower bound. Every node here stays inside the range it inherited, so the run ends valid. The invariant holds globally, not just between parents and children.
Next, the lowest common ancestor of 5 and 15. Both are less than 20, so the walk goes left; at 10 they split (5 is smaller, 15 is larger), and that split point is the answer. LCA is one downward walk with no backtracking.
Finally, the 3rd smallest key. The traversal is a plain in-order walk with a counter attached; it emits 5, then 10, then stops the moment the counter hits k = 3 at 15. Everything to the right of 15 is never touched.
What to Remember#
- The ordering invariant is global, not local. Every key in the left subtree must be smaller than the root, and every key in the right subtree must be larger, not just the immediate children.
- In-order traversal = sorted output. This is a direct consequence of the invariant and is the cleanest way to extract sorted data from a BST in O(n) time.
- Performance is tied to height. All core operations are O(h). Keep the tree balanced and you get O(log n); let it skew and you pay O(n). Self-balancing trees enforce balance automatically.