A binary search tree makes one promise — everything left is smaller, everything right is bigger — and that promise buys O(log n) search, a free sorted walk, and one-way answers to ancestor questions. This chapter cashes the bargain, then names the two shapes every tree recursion you'll ever write takes.
Chapter 11 gave you the traversals and promised that one throwaway fact — in-order on a BST comes out sorted — would solve three problems by itself. Time to collect. This chapter is half about the binary search tree's bargain, and half about something bigger: the two shapes that every tree recursion takes, which turn "write a recursive function" from improvisation into a fill-in-the-blanks form.
Canonical problems ahead: Validate Binary Search Tree Medium, Kth Smallest Element in a BST Medium, Lowest Common Ancestor of a BST Medium, Construct Binary Tree from Preorder and Inorder Traversal Medium, Subtree of Another Tree Easy, and a preview of Serialize and Deserialize Binary Tree Hard.
A binary search tree is a binary tree with one extra clause in its contract: at every node, everything in the left subtree is smaller, everything in the right subtree is bigger. Note the wording — everything in the subtree, not just the children. That distinction will earn a whole section, because it's where most wrong answers come from.
From that one clause, three superpowers fall out:
Insert and delete are searches with a small edit at the end, so they're O(h) too. Everything in this chapter is either cashing one of these three checks or learning to write the recursion that does.
To insert a value, search for it. You won't find it (assume unique values — and ask your interviewer about duplicates; it's a free clarifying question from Chapter 2's script). The search falls off the tree at exactly one empty spot, and that spot is where the new node belongs. The number of comparisons is the depth of that spot — that's the whole cost story.
Here's the uncomfortable part: the tree's shape is decided by arrival order, not by you. Values arriving in friendly shuffled order build a bushy tree with height around log n. Values arriving already sorted build a tree where every node has one child — a linked list with delusions of grandeur, height n, every superpower revoked.
Validate Binary Search Tree Medium hands you a tree and asks if the contract holds. The instinctive answer — check every node against its children, or every child against its parent — is the most famous wrong answer in the tree section of any question bank. It fails because the invariant is about ancestors, all of them: a node can be perfectly polite to its parent while betraying its grandparent.
Concretely: put 60 as the right child of 29, deep in the left subtree of 41. The parent check shrugs — 60 > 29, looks fine. But everything in 41's left subtree swore to stay below 41, and 60 didn't.
The fix is to make the promise explicit. Every node lives inside a window (lo, hi) assembled from its ancestors' values. The root's window is (−∞, +∞) — anything goes. Step left and the ceiling drops to the node's value; step right and the floor rises to it. A tree is a valid BST exactly when every node sits strictly inside its window. One pass, O(n) — every node checked once against a window it took O(1) to maintain.
Grow the tree below, then hit 💥 Corrupt: the widget plants exactly the grandparent-style lie above — a value that passes the parent-only check — and the window sweep walks the tree until the windows catch it.
Kth Smallest Element in a BST Medium sounds like it wants sorting, or a heap, or some clever order-statistics machinery. It wants none of that. The tree already is sorted — you just have to read it in the right order. Run an in-order walk with a counter initialized to k; decrement at every visit; when it hits zero, the node under your finger is the answer. Then — and this is the actual skill being tested — stop. Don't finish the traversal out of politeness.
That early exit makes the cost O(h + k) — walk down to the leftmost node, then k visits — instead of the O(n) of "collect everything into a list and index it". For k = 3 in a million-node tree, that's about twenty-three steps instead of a million. Same trick, mirrored, gives kth largest: run the walk right-node-left, so it comes out descending.
Drag k below and watch the countdown. The grey nodes are the point: they're the work you didn't do.
Lowest Common Ancestor of a Binary Search Tree Medium: given two nodes p and q, find the deepest node that has both of them in its subtree. On a general tree this needs real recursion — search both sides, combine reports. On a BST it needs a hallway walk, because the invariant answers the only question that matters at each node: which way do we both go?
No backtracking, no visited sets, not even recursion unless you feel like it — a while loop does fine. Cost: O(h) — one comparison per level, like everything the invariant touches — and O(1) space. The straddle case includes equality on purpose: if the walk lands on p, then p is an ancestor of q, and a node counts as its own ancestor in this problem (a clarification worth saying out loud).
Click any two nodes below, then watch the walk from the root find the split point.
Step back from BSTs for a moment, because this section is the one you'll reuse in every tree problem for the rest of your career. Every tree recursion moves information in one of two directions, and identifying the direction before you type writes the function signature for you.
Some problems use both at once — kth smallest carries the countdown "down" while the traversal reports "found it" back up; a shared counter is top-down information in a trench coat. That's fine. The point isn't purity; it's that you decide the direction first, and then the base case, parameters, and return type stop being creative decisions.
Construct Binary Tree from Preorder and Inorder Traversal Medium looks like a puzzle and is actually a division of labor. Preorder tells you who the root is — it's literally the first element, that's what "root first" means. Inorder tells you where the root sits — find it in the inorder list, and everything to its left is the left subtree, everything to its right is the right subtree. Now you have two smaller who-and-where pairs. Recurse. It's a top-down shape: the parameters are the boundaries of the slice you're rebuilding.
The one performance beat interviewers listen for: don't scan the inorder list for the root at every level — that's O(n²) on a degenerate tree. Build a hash map from value to inorder index once (Chapter 4 says hello) and every lookup is O(1), making the whole rebuild O(n).
Two relatives round out the family:
Here's the chapter folded into a decision you can make in the first ninety seconds. When a tree problem lands: first check whether the BST invariant can kill a subtree per step — search, LCA, insert, floor/ceiling, kth-with-early-exit all walk one path in O(h), and reaching for a full traversal there is leaving the discount on the table. If the invariant can't prune, you're visiting every node, and the only real decision left is the direction of information flow: down as parameters, or up as return values. Answer that, write the empty-tree base case, and the rest is transcription.
The pattern, as a whiteboard skeleton:
The flagship, in both languages: Validate Binary Search Tree Medium, solved twice through two different doors. The first door is the chapter's top-down shape — carry the (lo, hi) window as parameters, shrink it at every turn, fail the moment a node steps outside. The second door is Section 4's fact wearing a different hat: a real BST's in-order walk is strictly increasing, so just take the walk and watch for a stumble.
One sharp edge worth narrating in the room: initial bounds. Python's float("-inf") is a clean sentinel; in typed languages, using the type's own MinValue/MaxValue as sentinels breaks when a node legitimately holds that value — which is why the Scala version carries Option[Int] bounds, where "no bound yet" is a first-class state instead of a magic number.