Coding · Trees
Validate a Binary Search Tree
- Appears on company lists
- Medium
- 1 source
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
A binary tree arrives in level-order form, with null marking a missing child. Decide whether it is a valid binary search tree: for every node, all values in its left subtree must be strictly smaller and all values in its right subtree strictly larger, so duplicates make a tree invalid. For [10,5,15,null,null,6,20] the answer is false, because 6 is a fine left child of 15 yet sits in the right subtree of 10 while being smaller than 10. The tree has up to 100,000 nodes and may be a long chain. This is a guide level question: a prep guide gives it as its tree example for Zerodha, and no candidate report of it was found.
Restated in our own words, not a quote from Zerodha or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would start with the source: a prep guide lists this as its tree example for Zerodha, but I found no candidate report of it, so this is guide level practice on a standard question, not a reported one. Then the problem itself. Are duplicates allowed? (Here no, both sides are strict.) Is an empty tree valid? (Yes.) Can values be at the extremes of the integer range? How deep can the tree get, because a chain of 100,000 nodes would overflow a recursive walk in some languages?
Assumptions I would state: strict ordering on both sides, an empty tree is valid, values can be any integers, and the tree arrives as a level-order array that I turn into nodes first.
Brute force
Say the obvious answer and why it is too slow.
The direct reading of the rule is to check it node by node: for each node, scan its whole left subtree for a value that is not smaller and its whole right subtree for a value that is not larger. That is correct, but on a chain of 100,000 nodes the subtree sizes are 100,000, 99,999 and so on, around five billion steps in total, so O(n²).
The tempting shortcut is to compare each node only with its two children. It is fast and wrong: in the example, 6 is a valid child of 15, yet the tree is invalid. The rule is about whole subtrees, so information about ancestors has to travel downward.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(h) for the walk, O(n) with the built tree
The pattern is a tree walk that carries the allowed range. Every node must lie strictly between a low bound and a high bound. The root has no bounds. When we step to a left child, the high bound becomes the parent's value. When we step to a right child, the low bound becomes the parent's value. The other bound is inherited unchanged. A node is fine exactly when low < value < high, treating a missing bound as no limit.
Why is that enough? The BST rule says that for every ancestor a, the node is smaller than a if it lies in a's left subtree and larger than a if it lies in a's right subtree. Along the path from the root, the tightest upper limit is the nearest ancestor we turned left at, and the tightest lower limit is the nearest ancestor we turned right at. The bounds only ever narrow as we go down, so checking against the tightest pair also enforces every looser one.
I keep a missing bound as null instead of a huge number. A sentinel such as the largest integer would wrongly reject a tree whose node holds that very value. An explicit stack replaces recursion, so a chain of 100,000 nodes is safe, and pushing the right child before the left one makes the left side run first. The walk stops at the first violation it meets.
Out loud: "Each node carries the interval it must fall inside. Going left tightens the top of the interval, going right tightens the bottom."
Walk it through
A dry run on the example, step by step.
| Step | Node | Low | High | Verdict |
|---|---|---|---|---|
| 1 | 10 | none | none | ok |
| 2 | 5 | none | 10 | ok |
| 3 | 15 | 10 | none | ok |
| 4 | 6 | 10 | 15 | fails: 6 <= 10 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take [10,5,15,null,null,6,20]. The root 10 has no bounds and passes. Its left child 5 must be below 10 and passes. Its right child 15 must be above 10 and passes. Now 15's left child 6 is visited, and its interval is the low bound 10 from the root and the high bound 15 from its parent. Since 6 is not above 10, the walk stops and returns false. Node 20 is never checked.
A local check would have accepted 6, because 6 is below its parent 15. Only the bound inherited from the root catches it.
The code
Runnable JavaScript, checked against test cases.
function isValidBst(values) {
if (values.length === 0 || values[0] === null) return true;
const pending = [{ node: buildTree(values), low: null, high: null }];
while (pending.length > 0) {
const { node, low, high } = pending.pop();
if (low !== null && node.val <= low) return false;
if (high !== null && node.val >= high) return false;
if (node.right !== null) pending.push({ node: node.right, low: node.val, high });
if (node.left !== null) pending.push({ node: node.left, low, high: node.val });
}
return true;
}
function buildTree(values) {
const root = { val: values[0], left: null, right: null };
const waiting = [root];
let next = 1;
for (let head = 0; head < waiting.length && next < values.length; head++) {
for (const side of ["left", "right"]) {
if (next >= values.length) break;
const value = values[next++];
if (value === null) continue;
waiting[head][side] = { val: value, left: null, right: null };
waiting.push(waiting[head][side]);
}
}
return root;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty tree: an empty array, or an array whose first value is null, is valid.
- Single node: no bounds apply, so it is valid.
- Duplicates: an equal value on either side fails because both comparisons are strict, so [2,2,2] is invalid.
- Extreme values: missing bounds are null, so a node holding the smallest or largest integer is still handled.
- Long chains: the explicit stack means depth cannot overflow the call stack. A chain that always goes right never holds more than one pending node.
- Violation deep in a branch: a node far below an ancestor that it breaks is caught, as 6 is in the example, because bounds travel with the walk.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it with an in-order traversal, and what must you remember between steps to detect a duplicate?
- How would you repair a tree in which exactly two nodes were swapped by mistake, without changing its shape?
- How would you return the size of the largest subtree that is itself a valid BST?
- How would the check change if duplicates were allowed on the left side only?
Where candidates slip
The mistakes this problem punishes.
The classic slip is comparing a node only with its own children, which accepts trees where a deep node breaks an ancestor's rule.
- Using less-or-equal where the rule is strict, which accepts duplicates.
- Using the integer limits as stand-in bounds, which fails for a node holding exactly that limit.
- Updating only one bound when moving down, for example passing the parent's value as the new low bound when going left.
- Checking that the left child is smaller and the right child is larger, then recursing without passing any bounds.
- Recursing on a 100,000-node chain in a language with a small call stack.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.