28. Validate Binary Search Tree
mediumAsked at AppleVerify that every node in a binary tree satisfies the full BST invariant — not just against its children, but against ALL its ancestors. That distinction is the entire question: the locally-correct-but-globally-wrong tree is interviewing's favorite trap. Apple candidates report it as a core screen for roles touching sorted structures, where the graded move is spotting why the naive child-only check fails and replacing it with min/max bound propagation.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Apple loops.
- LeetCode (2026)— Problem #98 'Validate Binary Search Tree' — canonical statement and the INT_MIN/INT_MAX boundary cases; a perennial top-asked tree question.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Apple interview prep.
Problem
Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as: the left subtree of a node contains only nodes with keys less than the node's key; the right subtree contains only nodes with keys greater than the node's key; and both subtrees must also be valid BSTs.
Constraints
The number of nodes in the tree is in the range [1, 10^4]-2^31 <= Node.val <= 2^31 - 1Node values may include INT_MIN and INT_MAX — use null bounds, not numeric sentinels
Examples
Example 1
root = [2,1,3]trueExample 2
root = [5,1,4,null,null,3,6]falseExplanation: Root's right child 4 is less than root 5
Approaches
1. Naive recursive (left/right child only)
Check only immediate children. WRONG — fails for nodes violating ancestor bounds deep in the tree.
- Time
- O(n)
- Space
- O(h)
// INCORRECT — included to illustrate the common mistake
function isValidBST(root) {
if (!root) return true;
if (root.left && root.left.val >= root.val) return false;
if (root.right && root.right.val <= root.val) return false;
return isValidBST(root.left) && isValidBST(root.right);
}Tradeoff: Looks right, passes shallow tests, and is wrong: a node can satisfy its parent while violating a grandparent's bound (the 6 under 15 in [10,5,15,null,null,6,20]). Its only interview value is being the wrong answer you can explain — which is exactly how interviewers deploy it.
2. Bounded DFS (min/max propagation)
Pass valid range [min, max] down the recursion. Each node must lie strictly within its inherited bounds — this catches violations anywhere in the tree.
- Time
- O(n)
- Space
- O(h)
function isValidBST(root) {
const validate = (node, min, max) => {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
};
return validate(root, -Infinity, Infinity);
}Tradeoff: Linear time, recursion-depth space, and every ancestor constraint is enforced because the bounds tighten on the way down. The equally-valid alternative is an inorder traversal checking strict increase — mention both and note the bounds version needs no extra state between siblings.
Apple-specific tips
Apple interviewers almost always present the naive solution first and ask 'is this correct?' — they want to see you spot the ancestor-bound violation. The tree [10, 5, 15, null, null, 6, 20] is a canonical trap: 6 is left-child of 15 and looks locally valid, but violates root's right-subtree constraint. Walk through this example proactively. Use null bounds (−∞/+∞) rather than INT_MIN/INT_MAX to handle nodes whose values are exactly at integer boundaries — Apple hardware teams care about edge cases at machine limits.
Common mistakes
- Checking only immediate children — the grandparent-bound violation is THE designed trap of this problem.
- Using INT_MIN/INT_MAX as initial bounds — a node valued exactly at the integer boundary then falsely fails; use -Infinity/Infinity or nullable bounds.
- Allowing equality (node.val <= min vs <) — BST keys here are strict; duplicates make the tree invalid.
- In the inorder variant, comparing against the previous VALUE initialized to a sentinel instead of tracking 'has previous' — same boundary bug in different clothes.
Follow-up questions
An interviewer at Apple may pivot to one of these next:
- Recover Binary Search Tree (LC 99): two nodes were swapped — find them via the inorder sequence's two inversions.
- Kth Smallest Element in a BST (LC 230): the inorder traversal you just defended, applied to selection.
- Validate at scale: how would you check a billion-node sorted index without recursion? (Iterative inorder with an explicit stack, or Morris traversal for O(1) space.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does the child-only check fail?
BST ordering is a GLOBAL property: every node in a left subtree must be smaller than every ancestor it descends left from. A node can be fine relative to its parent while breaking a bound set three levels up — only propagated min/max bounds (or a full inorder scan) see that.
Is the inorder-traversal solution equally acceptable?
Yes — a BST is valid iff its inorder sequence is strictly increasing, so traverse while comparing each value to the previous one. Same O(n) time and O(h) space; interviewers accept either and often ask for whichever one you didn't write.
How do duplicates affect the answer?
This problem defines validity with STRICT inequalities, so any duplicate key invalidates the tree. If a variant allows duplicates on one side, the bound propagation changes one comparison — say which side and why before coding.