Pattern 3: Binary search tree (BST)
A BST is a binary tree with a golden rule: for every node, everything to the left is smaller and everything to the right is larger. That single rule gives search, insertion and removal in O(h) — and reveals a magical property in the in-order traversal.
Try it first: Validate Binary Search Tree
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Check whether a binary tree is a valid BST: for every node, all values in the left subtree are smaller than it, and all values in the right are greater — recursively.
Example: [2,1,3] → true. [5,1,4,null,null,3,6] → false (3 and 6 are to the right of 5, but 3 < 5).
Did you try? Mistake #1 is comparing each node only with its direct children — and passing trees that are not valid BSTs. The theory below shows why you must think in terms of ranges.
The theory: the rule holds for the whole subtree
The BST rule is not local ("greater than the parent") — it is global: all of a node's left subtree is smaller than it, and all of the right is larger. That is why validating by comparing only parent and child fails:
5
/ \
1 4 ← 4 < 5? yes. But 4 is to the RIGHT of 5...
/ \ ...and 3 < 5 too! It is NOT a valid BST.
3 6
The correct way: each node has an allowed range (min, max) that
narrows as you descend. When going left, the node's value becomes the
new max; when going right, it becomes the new min:
valid(node, min, max):
if node is None → True
if not (min < node.val < max) → False
return valid(node.left, min, node.val) and valid(node.right, node.val, max)
The magical property: in-order = ascending order
Remember the traversals (lesson 1)? In a BST, the in-order traversal (left → node → right) visits the values in ascending order. It makes sense: you always visit everything smaller (left) before the node, and everything larger (right) after. This solves a family of problems — Kth Smallest Element, for example, is just "stop at the k-th visit of the in-order traversal".
Search in a BST: O(h)
Looking for a value in a BST is like binary search (the Binary section!): compare with the node; if the target is smaller, go left; if larger, go right. Each step discards half the tree (a whole subtree). Watch the search go down — note how it skips whole branches:
It costs O(h): log n in a balanced tree, n in a degenerate one. It is the same "cut in half" logic as binary search, now on the tree's structure.
Notice the LCA (lowest common ancestor) in a BST: it is the node where the
values p and q "split" (one goes left, the other right, or one of them is
the node itself). The BST rule tells you exactly which way each one goes — so
we find the LCA in O(h) just by descending.
The lesson
The BST rule (left < node < right, for the whole subtree) is what turns an ordinary tree into a search structure. Whenever you see "BST" in the statement, think: (1) can I use the rule to descend down only one side (O(h) search)? (2) does the in-order (ascending) traversal help?
🧠 Review quiz
0/41. What is the rule that defines a BST?
2. Why is validating a BST by comparing each node only with its direct children wrong?
3. What order does the in-order traversal produce in a BST, and why?
4. Why is search in a BST O(h)?
Summary
- BST: left < node < right, for the whole subtree (global rule).
- Validating requires a range (min, max) that narrows as you descend — not just comparing parent/child.
- In-order traversal = ascending (solves Kth Smallest).
- Search/LCA in O(h), descending only one side — the binary search of trees.
Next lesson: rebuilding and serializing trees.