Pattern this teaches:Binary Search Tree Problems
Validate Binary Search Tree
A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 3
- Core for
- 2 roles
The problem
Check whether a binary tree obeys the search-tree rule at every node: all values in a node's left subtree are strictly smaller than the node, and all values in its right subtree are strictly larger. Comparing a node with its two children alone is not enough; the rule covers whole subtrees.
Example 1
- Input
- [8,5,12,3,6,10,14]
- Output
- true
- Why
- Every left descendant stays smaller than its ancestors and every right one larger.
Example 2
- Input
- [10,6,15,4,12,13,20]
- Output
- false
- Why
- 12 sits in 10's left subtree but is greater than 10.
Example 3
- Input
- [1]
- Output
- true
- Why
- A single node is always a valid BST.
Constraints
- The number of nodes is in the range [1, 104].
- -231 <= Node.val <= 231 - 1
How to think about it
Updated 2026-09-29Checking only that each node is bigger than its left child and smaller than its right child is the classic trap: it lets invalid values slip deep into subtrees. The true BST condition is that every node must fit inside an inherited open interval (low, high) tightened by its ancestors, or equivalently, an inorder traversal must be strictly increasing.
Approaches, worst first
Collect and check sorted
time O(n) · space O(n)
Run a full inorder traversal into an array, then scan to confirm strict ascending order. Clean and quick to verify, but it allocates heap memory for all nodes and cannot stop early on the first violation it encounters.
Inorder walk with previous pointer
time O(n) · space O(h)
Traverse inorder iteratively or recursively while holding only the previous node's value. Return false the instant a value does not strictly exceed the predecessor. Prunes early and needs space only for the recursion stack.
Recursive range narrowingWrite this one
time O(n) · space O(h)
Pass an allowed range (minVal, maxVal) down the call tree, starting with infinite bounds. Check the root against the current bounds, then branch left narrowing the upper limit and right narrowing the lower limit. It stops as soon as an anomaly is seen.
Where people lose marks · 3
- Comparing only immediate children. A tree with root 10, right child 15, and 15 having left child 6 satisfies local child checks but violates the whole-tree invariant.
- Allowing duplicate values. A strict BST requires left < node < right; checking `<=` mistakenly accepts duplicates.
- Using 32-bit signed integer limits for initial bounds. Because Node.val can reach -2^31 or 2^31 - 1, a root equal to a limit causes false rejections; use 64-bit integers or null sentinel bounds.
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .