Search and Validate

What is this?

These problems ask you to find a value in a BST or check that a tree is a valid BST at all. The trick is that you never wander the whole tree — at each node you compare, then step left or right, throwing away the side that cannot hold your answer. It is the same "higher or lower?" guessing game that makes searching feel almost instant.

💡 Fun fact: The most common BST validation bug is checking each node only against its direct children. A node can look fine next to its parent yet still break the order rule against a far-away ancestor — so you must pass down a running low-high window.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: A binary search tree stores a global ordering locally — everything in the left subtree is smaller, everything in the right subtree is larger. That single invariant lets you make a decision at each node and discard the half you don't need, turning a tree walk into a directed descent. Every problem here is the same move dressed differently: compare against the node, then commit to one side (or prune it entirely).

The pattern

The BST invariant means each node splits the remaining keys into a smaller-left and larger-right block. So instead of exploring the whole tree, you branch on a comparison: too big means go left, too small means go right. That is an O(h) descent — O(log n) on a balanced tree, O(n) in the worst case when it degenerates into a chain.

Two views of the same invariant power this chapter. The bounds view carries a (low, high) window down each path and asks whether every node stays inside it. The inorder view observes that visiting left, then node, then right yields the keys in strictly increasing order. Whenever you need to validate, prune, or step toward a target, reach for one of these two lenses.

The problems

• Validate Binary Search Tree — the definitional check. Either confirm the inorder walk is strictly sorted, or push a (low, high) bounds window down each path and verify every node fits. The trap is checking only a node against its immediate children instead of against the inherited window.
• Closest Binary Search Tree Value — walk toward the target: at each node compare to the target, track the best-so-far, and descend left or right. The ordering guarantees the closest value lies along the single root-to-leaf path you take.
• Range Sum of BST — sum the keys inside [low, high] while pruning by bounds: if the node is below low, skip its left subtree entirely; if above high, skip its right. The invariant tells you whole subtrees cannot contribute.
• First Bad Version — note this is binary search on a monotonic predicate, not a true BST. There is no tree; you bisect a sorted version range where "bad" flips from false to true exactly once. It lives here because it shares the same halve-and-commit instinct.

Key takeaways

• The invariant is the algorithm: smaller-left, larger-right lets you discard half the keys at every step.
• Two lenses cover everything here — a (low, high) bounds window, or the strictly increasing inorder sequence.
• Validate against the inherited window, not just the immediate children — the classic BST validation bug.
• Prune whole subtrees when an entire range falls outside your target interval.
• First Bad Version is binary search, not a BST — same halving instinct, no tree involved.
• Cost is O(h): O(log n) when balanced, O(n) when the tree degenerates into a chain.

Order: Validate Binary Search Tree → Closest Binary Search Tree Value → Range Sum of BST → First Bad Version.