What it is
A binary search tree adds one structural promise on top of a plain binary tree: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. That single invariant is what lets you skip an entire subtree during a search instead of visiting every node, and it means an inorder traversal (left, node, right) visits values in strictly ascending order for free. BST problems are really about spending that invariant deliberately — deciding at each node which side can be ignored, or exploiting the fact that "in sorted order" and "inorder traversal" mean the same thing here.
When it applies
- You need to search for, insert, or bound a value and can rule out one whole subtree at each step by comparing against the current node.
- You need the k-th smallest/largest value, a sorted sequence of values, or a running position in sorted order — all of these come from an inorder traversal for free, without sorting anything.
- You're finding the ancestor relationship between two nodes and can use the ordering to decide which direction to go, rather than searching both subtrees.
- If the tree is not guaranteed to satisfy the BST invariant, none of these shortcuts are valid, and you're back to plain tree DFS — checking that invariant (with the right open-interval bounds, not just comparing to a node's immediate children) is itself a common problem in this hub.
Tells in the problem
- "Given the root of a binary search tree" stated explicitly, distinguishing it from a plain binary tree problem.
- "k-th smallest" or "k-th largest," where the ordering lets you stop an inorder walk early instead of collecting every value.
- An iterator or "next smallest value" API, which asks you to pause and resume an inorder traversal instead of materializing it all up front.
- Two node values being compared against the current node's value to decide whether to go left, right, or stop — a hallmark of exploiting the invariant rather than searching both children.
- "Decide whether this is a valid BST" — a check of the invariant itself, which needs a running valid range, not just a parent-child comparison.
The classic mistake
Validating a BST by only checking a node against its immediate children (left child smaller, right child larger) instead of against the full range of values that are allowed at that position — a node three levels down in a left subtree must be smaller than every ancestor above it that it's under the left side of, not just its direct parent, so a local check misses violations from higher up. The general BST mistake this generalizes to: using the invariant only one level deep instead of carrying the accumulated bound (a valid (low, high) range, passed down and narrowed at each step) through the whole recursion. Notice this in yourself whenever a BST solution compares only to node.val or node.left.val without also referencing bounds inherited from further up the tree.
Questions to start with
- Validate Binary Search Tree — the invariant itself: carrying a shrinking valid range down the recursion instead of checking only immediate children.
- Kth Smallest Element in a BST — the inorder-traversal-is-sorted-order idea, stopping early once the k-th value is reached.
- Lowest Common Ancestor of a Binary Search Tree — using the ordering to pick a single direction at each node instead of searching both subtrees.
- Binary Search Tree Iterator — the hardest of the set: pausing and resuming an inorder traversal with an explicit stack instead of a generator, to hit the O(h)-memory requirement.