Implement binarySearchTreeValidate(root) — return true if the binary tree rooted at root is a valid binary search tree (BST), and false otherwise. A BST is a tree where every node's value is greater than every value in its left subtree and less than every value in its right subtree. That whole-subtree ordering is what lets you find, insert, and delete a value in O(height) time instead of scanning every node — it's the invariant behind ordered maps and sets in many standard libraries.
// A tree node:
// { val: number, left: Node | null, right: Node | null }
// root: Node | null — the root of the tree, or null for an empty tree.
// returns: boolean — true if the tree is a valid BST, false otherwise.
function binarySearchTreeValidate(root): boolean;A leaf is a node whose left and right are both null. An empty tree is root === null.
// A valid BST: every left descendant < its ancestor < every right descendant.
// 5
// / \
// 3 8
// / \
// 1 4
const valid = {
val: 5,
left: { val: 3, left: { val: 1, left: null, right: null },
right: { val: 4, left: null, right: null } },
right: { val: 8, left: null, right: null },
};
binarySearchTreeValidate(valid); // → true// NOT a BST, even though each node looks fine next to its own children.
// 5
// \
// 7
// /
// 4 ← 4 sits in 5's RIGHT subtree, but 4 < 5
const sneaky = {
val: 5,
left: null,
right: { val: 7, left: { val: 4, left: null, right: null }, right: null },
};
binarySearchTreeValidate(sneaky); // → falseIn the second tree, 7 > 5 (good as 5's right child) and 4 < 7 (good as 7's left child). Every parent–child pair is locally ordered. But 4 lives somewhere in 5's right subtree, and the BST rule says everything there must exceed 5. It doesn't. So the tree is invalid — a fact you cannot see by only comparing a node to its immediate children.
{ val: 5, left: { val: 5, ... } }) makes the tree invalid here. (Some definitions allow duplicates on one side — we don't; treat equal values as a violation.)binarySearchTreeValidate(null) returns true.true.NaN, non-numeric values, cycles, or parent pointers — the input is always a finite binary tree of numbers.You'll walk a binary tree once and decide whether it obeys the binary search tree ordering rule, carrying down the range of values each node is allowed to hold.
A binary search tree is the structure that makes a phone book fast. Every node splits the remaining values into "smaller, go left" and "larger, go right," so a lookup throws away half the tree at each step instead of scanning every entry. That speed depends entirely on one promise: at every node, all of the left subtree is smaller and all of the right subtree is larger. Validation is checking that the promise actually holds — because if even one value is in the wrong subtree, every search that passes through that node can silently miss the value it's looking for.
The catch is the word all. It's tempting to read the rule as "left child smaller, right child larger" and check just the two children of each node. That weaker rule is not the same thing, and the gap between them is the entire point of this question.
Forget children for a moment and think about windows. Every node is allowed to hold a value only inside some open interval (low, high). The root may hold anything, so its window is (-∞, +∞). The instant you step into a child, the window tightens: the parent's value becomes a hard wall on one side. Step left and the parent is the new ceiling (high); step right and the parent is the new floor (low). A node is valid exactly when its value lands strictly inside the window it inherited — and crucially, a wall set high up in the tree keeps applying all the way down, because the window only ever shrinks.
That picture is the whole solution. The hard part is resisting the simpler-looking idea first.
The obvious move is to encode the rule literally as you understood it on first read: a node's left child is smaller, its right child is larger. Recurse, and at each node check the two children that are right there in front of you.
function validateChildrenOnly(root) {
if (root === null) return true;
// Compare the node only to its immediate children.
if (root.left && root.left.val >= root.val) return false;
if (root.right && root.right.val <= root.val) return false;
// Then recurse into each child the same way.
return validateChildrenOnly(root.left) && validateChildrenOnly(root.right);
}This passes a lot of trees, which is exactly why it's dangerous. Run it on the tree { 5, right: { 7, left: { 4 } } }. At the root, 5 has no left child and its right child 7 satisfies 7 > 5 — fine. Recurse into 7: its left child 4 satisfies 4 < 7 — also fine. There's no node left to reject, so the function returns true. But 4 sits inside 5's right subtree, where everything must be greater than 5, and 4 < 5. The tree is not a valid BST, and the child-only check waved it straight through.
The bug is structural, not a typo: comparing a node to its children only ever enforces a constraint one level deep. A value that's wrong relative to a grandparent or any deeper ancestor is never checked against that ancestor at all. The rule is about whole subtrees; a one-level check can't express it.
The fix is to stop comparing nodes to their neighbours and start carrying the window down the recursion. Each call receives the (low, high) interval its node must fall inside. The node validates itself against that interval, then hands each child a tightened copy.
function binarySearchTreeValidate(root) {
// Each node must lie strictly inside an open interval (low, high).
// The root has no bound on either side, so we start with (-∞, +∞).
function check(node, low, high) {
if (node === null) return true; // empty slot can't violate anything
// node.val must sit strictly between the inherited bounds.
if (node.val <= low || node.val >= high) return false;
// Going left, node becomes the new upper bound (everything left is < node.val).
// Going right, node becomes the new lower bound (everything right is > node.val).
return (
check(node.left, low, node.val) &&
check(node.right, node.val, high)
);
}
return check(root, -Infinity, Infinity);
}
module.exports = { binarySearchTreeValidate };The shift from the naive version is small in code and total in meaning. The naive check asked "is this node ordered against its children?" This one asks "is this node ordered against every ancestor that constrains it?" — and it answers that by threading the accumulated bounds through the arguments instead of trying to read them off the tree. A few choices are worth pinning down:
Why <= and >=, not < and >. The interval is open — the node must be strictly inside it. node.val <= low rejects a value equal to a lower bound; node.val >= high rejects one equal to an upper bound. This is what makes duplicates invalid: when a left child equals its parent, the parent has been passed down as high, so child.val >= high fires and we return false. Flip these to strict </> and equal values would slip through, quietly allowing the duplicate trees the spec forbids.
Why the bounds start at -Infinity and +Infinity. The root is constrained by nothing, so its window must accept any finite number. JavaScript's -Infinity/Infinity are real numeric values you can compare against, and since the problem guarantees finite node values, no real value ever equals them — 5 <= -Infinity is false, 5 >= Infinity is false, so the root always passes the bound check and moves on to its children.
Why null returns true. A missing child is an empty subtree, and an empty subtree violates nothing. Returning true for null is also what terminates the recursion — every path down the tree eventually reaches a null and stops. The base case does double duty: it's both "empty trees are valid" and "we've hit the bottom."
Why we narrow exactly one side per step. Going left, the current node is the largest value allowed below-left, so it replaces high while low rides along unchanged. Going right, the node is the smallest value allowed below-right, so it replaces low and high rides along. The side that doesn't change is the one carrying a bound set by some ancestor — that's the mechanism that lets 5 keep constraining 4 two levels down.
The whole tree is visited once, each node does O(1) work, so the algorithm runs in O(n) time for n nodes. The only extra space is the recursion stack, which goes as deep as the tree is tall — O(h), from O(log n) on a balanced tree up to O(n) on a fully skewed one.
Take the deep-violator tree and watch the bound do the work the child-only check couldn't: { val: 5, right: { val: 7, left: { val: 4 } } }.
check(5, -∞, +∞) 5 inside (-∞, +∞)? yes.
left is null → check(null, -∞, 5) → true
recurse right with low raised to 5:
check(7, 5, +∞) 7 inside (5, +∞)? yes (7 > 5).
recurse left with high lowered to 7:
check(4, 5, 7) 4 inside (5, 7)?
4 <= 5 (low) → TRUE → return false
↑ the grandparent's floor of 5 catches it
check(7, ...) returns false && check(null, 7, +∞) → false
check(5, ...) returns true && false → false
binarySearchTreeValidate → false
The decisive line is check(4, 5, 7). By the time we reach 4, its window is (5, 7): the 7 is its parent (lowered into high on the left step), and the 5 is its grandparent (still sitting in low because the right step never touched the low bound). 4 <= 5 trips the lower-bound guard, and the false short-circuits back up through the && chain to the root. The exact bound the naive version never checked — 4 against 5 — is the one that rejects the tree.
Contrast a valid input briefly: on { 5, left: { 3, left: { 1 }, right: { 4 } } }, the call check(4, 3, 5) asks "is 4 inside (3, 5)?" — yes — and that node passes precisely because both its parent (3, the floor) and its grandparent (5, the ceiling) agree it belongs there.
{ 5, right: { 7, left: { 4 } } } as valid. A node bounds its entire subtree, not just its two children. Fix: thread (low, high) bounds down the recursion so every ancestor's wall keeps applying.</> and accidentally allowing duplicates. The interval is open, so the comparison must be <=/>= to reject a value equal to a bound. With strict </>, a child equal to its parent ({ 5, left: { 5 } }) sneaks through, since 5 < 5 is false. Fix: reject on node.val <= low || node.val >= high so equal values fail, matching the strict-inequality spec.null or 0 instead of ±Infinity. If you start low/high as null and write node.val <= low, the comparison coerces null to 0 and silently rejects every negative root value (and corrupts the logic for positives too). Starting at 0 is worse — a perfectly valid tree of negative numbers fails. Fix: seed with -Infinity and Infinity, real numeric sentinels no finite value equals.null base case. Reading node.val when node is null throws TypeError: Cannot read properties of null. Every leaf has two null children, so this fires on the very first real tree. Fix: if (node === null) return true as the first line — empty subtrees are valid and it's also what ends the recursion.true/false plus a [min, max] from each subtree and combining at the parent works, but it's fiddly: you must merge child ranges, guard empty subtrees, and get the comparison direction right at every join. The top-down bound-passing version expresses the same invariant with far less to get wrong; reach for it first.false the moment the current value isn't strictly greater than the previous one. It's O(n) time and lets you bail early on the first out-of-order pair; the only state you carry is one prev variable instead of a pair of bounds.n deep). Convert it to a loop by pushing [node, low, high] triples onto an explicit array-stack and processing them yourself — same logic, same bounds, but the depth lives in heap memory you control instead of the JS engine's call stack.BSTIterator class that exposes next()/hasNext() over the in-order sequence, holding only the path of "controlled-recursion" stack frames down to the current node (O(h) space). Validation then becomes "are successive next() values strictly increasing?", and the same iterator powers ordered traversal everywhere else.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Implement binarySearchTreeValidate(root) — return true if the binary tree rooted at root is a valid binary search tree (BST), and false otherwise. A BST is a tree where every node's value is greater than every value in its left subtree and less than every value in its right subtree. That whole-subtree ordering is what lets you find, insert, and delete a value in O(height) time instead of scanning every node — it's the invariant behind ordered maps and sets in many standard libraries.
// A tree node:
// { val: number, left: Node | null, right: Node | null }
// root: Node | null — the root of the tree, or null for an empty tree.
// returns: boolean — true if the tree is a valid BST, false otherwise.
function binarySearchTreeValidate(root): boolean;A leaf is a node whose left and right are both null. An empty tree is root === null.
// A valid BST: every left descendant < its ancestor < every right descendant.
// 5
// / \
// 3 8
// / \
// 1 4
const valid = {
val: 5,
left: { val: 3, left: { val: 1, left: null, right: null },
right: { val: 4, left: null, right: null } },
right: { val: 8, left: null, right: null },
};
binarySearchTreeValidate(valid); // → true// NOT a BST, even though each node looks fine next to its own children.
// 5
// \
// 7
// /
// 4 ← 4 sits in 5's RIGHT subtree, but 4 < 5
const sneaky = {
val: 5,
left: null,
right: { val: 7, left: { val: 4, left: null, right: null }, right: null },
};
binarySearchTreeValidate(sneaky); // → falseIn the second tree, 7 > 5 (good as 5's right child) and 4 < 7 (good as 7's left child). Every parent–child pair is locally ordered. But 4 lives somewhere in 5's right subtree, and the BST rule says everything there must exceed 5. It doesn't. So the tree is invalid — a fact you cannot see by only comparing a node to its immediate children.
{ val: 5, left: { val: 5, ... } }) makes the tree invalid here. (Some definitions allow duplicates on one side — we don't; treat equal values as a violation.)binarySearchTreeValidate(null) returns true.true.NaN, non-numeric values, cycles, or parent pointers — the input is always a finite binary tree of numbers.You'll walk a binary tree once and decide whether it obeys the binary search tree ordering rule, carrying down the range of values each node is allowed to hold.
A binary search tree is the structure that makes a phone book fast. Every node splits the remaining values into "smaller, go left" and "larger, go right," so a lookup throws away half the tree at each step instead of scanning every entry. That speed depends entirely on one promise: at every node, all of the left subtree is smaller and all of the right subtree is larger. Validation is checking that the promise actually holds — because if even one value is in the wrong subtree, every search that passes through that node can silently miss the value it's looking for.
The catch is the word all. It's tempting to read the rule as "left child smaller, right child larger" and check just the two children of each node. That weaker rule is not the same thing, and the gap between them is the entire point of this question.
Forget children for a moment and think about windows. Every node is allowed to hold a value only inside some open interval (low, high). The root may hold anything, so its window is (-∞, +∞). The instant you step into a child, the window tightens: the parent's value becomes a hard wall on one side. Step left and the parent is the new ceiling (high); step right and the parent is the new floor (low). A node is valid exactly when its value lands strictly inside the window it inherited — and crucially, a wall set high up in the tree keeps applying all the way down, because the window only ever shrinks.
That picture is the whole solution. The hard part is resisting the simpler-looking idea first.
The obvious move is to encode the rule literally as you understood it on first read: a node's left child is smaller, its right child is larger. Recurse, and at each node check the two children that are right there in front of you.
function validateChildrenOnly(root) {
if (root === null) return true;
// Compare the node only to its immediate children.
if (root.left && root.left.val >= root.val) return false;
if (root.right && root.right.val <= root.val) return false;
// Then recurse into each child the same way.
return validateChildrenOnly(root.left) && validateChildrenOnly(root.right);
}This passes a lot of trees, which is exactly why it's dangerous. Run it on the tree { 5, right: { 7, left: { 4 } } }. At the root, 5 has no left child and its right child 7 satisfies 7 > 5 — fine. Recurse into 7: its left child 4 satisfies 4 < 7 — also fine. There's no node left to reject, so the function returns true. But 4 sits inside 5's right subtree, where everything must be greater than 5, and 4 < 5. The tree is not a valid BST, and the child-only check waved it straight through.
The bug is structural, not a typo: comparing a node to its children only ever enforces a constraint one level deep. A value that's wrong relative to a grandparent or any deeper ancestor is never checked against that ancestor at all. The rule is about whole subtrees; a one-level check can't express it.
The fix is to stop comparing nodes to their neighbours and start carrying the window down the recursion. Each call receives the (low, high) interval its node must fall inside. The node validates itself against that interval, then hands each child a tightened copy.
function binarySearchTreeValidate(root) {
// Each node must lie strictly inside an open interval (low, high).
// The root has no bound on either side, so we start with (-∞, +∞).
function check(node, low, high) {
if (node === null) return true; // empty slot can't violate anything
// node.val must sit strictly between the inherited bounds.
if (node.val <= low || node.val >= high) return false;
// Going left, node becomes the new upper bound (everything left is < node.val).
// Going right, node becomes the new lower bound (everything right is > node.val).
return (
check(node.left, low, node.val) &&
check(node.right, node.val, high)
);
}
return check(root, -Infinity, Infinity);
}
module.exports = { binarySearchTreeValidate };The shift from the naive version is small in code and total in meaning. The naive check asked "is this node ordered against its children?" This one asks "is this node ordered against every ancestor that constrains it?" — and it answers that by threading the accumulated bounds through the arguments instead of trying to read them off the tree. A few choices are worth pinning down:
Why <= and >=, not < and >. The interval is open — the node must be strictly inside it. node.val <= low rejects a value equal to a lower bound; node.val >= high rejects one equal to an upper bound. This is what makes duplicates invalid: when a left child equals its parent, the parent has been passed down as high, so child.val >= high fires and we return false. Flip these to strict </> and equal values would slip through, quietly allowing the duplicate trees the spec forbids.
Why the bounds start at -Infinity and +Infinity. The root is constrained by nothing, so its window must accept any finite number. JavaScript's -Infinity/Infinity are real numeric values you can compare against, and since the problem guarantees finite node values, no real value ever equals them — 5 <= -Infinity is false, 5 >= Infinity is false, so the root always passes the bound check and moves on to its children.
Why null returns true. A missing child is an empty subtree, and an empty subtree violates nothing. Returning true for null is also what terminates the recursion — every path down the tree eventually reaches a null and stops. The base case does double duty: it's both "empty trees are valid" and "we've hit the bottom."
Why we narrow exactly one side per step. Going left, the current node is the largest value allowed below-left, so it replaces high while low rides along unchanged. Going right, the node is the smallest value allowed below-right, so it replaces low and high rides along. The side that doesn't change is the one carrying a bound set by some ancestor — that's the mechanism that lets 5 keep constraining 4 two levels down.
The whole tree is visited once, each node does O(1) work, so the algorithm runs in O(n) time for n nodes. The only extra space is the recursion stack, which goes as deep as the tree is tall — O(h), from O(log n) on a balanced tree up to O(n) on a fully skewed one.
Take the deep-violator tree and watch the bound do the work the child-only check couldn't: { val: 5, right: { val: 7, left: { val: 4 } } }.
check(5, -∞, +∞) 5 inside (-∞, +∞)? yes.
left is null → check(null, -∞, 5) → true
recurse right with low raised to 5:
check(7, 5, +∞) 7 inside (5, +∞)? yes (7 > 5).
recurse left with high lowered to 7:
check(4, 5, 7) 4 inside (5, 7)?
4 <= 5 (low) → TRUE → return false
↑ the grandparent's floor of 5 catches it
check(7, ...) returns false && check(null, 7, +∞) → false
check(5, ...) returns true && false → false
binarySearchTreeValidate → false
The decisive line is check(4, 5, 7). By the time we reach 4, its window is (5, 7): the 7 is its parent (lowered into high on the left step), and the 5 is its grandparent (still sitting in low because the right step never touched the low bound). 4 <= 5 trips the lower-bound guard, and the false short-circuits back up through the && chain to the root. The exact bound the naive version never checked — 4 against 5 — is the one that rejects the tree.
Contrast a valid input briefly: on { 5, left: { 3, left: { 1 }, right: { 4 } } }, the call check(4, 3, 5) asks "is 4 inside (3, 5)?" — yes — and that node passes precisely because both its parent (3, the floor) and its grandparent (5, the ceiling) agree it belongs there.
{ 5, right: { 7, left: { 4 } } } as valid. A node bounds its entire subtree, not just its two children. Fix: thread (low, high) bounds down the recursion so every ancestor's wall keeps applying.</> and accidentally allowing duplicates. The interval is open, so the comparison must be <=/>= to reject a value equal to a bound. With strict </>, a child equal to its parent ({ 5, left: { 5 } }) sneaks through, since 5 < 5 is false. Fix: reject on node.val <= low || node.val >= high so equal values fail, matching the strict-inequality spec.null or 0 instead of ±Infinity. If you start low/high as null and write node.val <= low, the comparison coerces null to 0 and silently rejects every negative root value (and corrupts the logic for positives too). Starting at 0 is worse — a perfectly valid tree of negative numbers fails. Fix: seed with -Infinity and Infinity, real numeric sentinels no finite value equals.null base case. Reading node.val when node is null throws TypeError: Cannot read properties of null. Every leaf has two null children, so this fires on the very first real tree. Fix: if (node === null) return true as the first line — empty subtrees are valid and it's also what ends the recursion.true/false plus a [min, max] from each subtree and combining at the parent works, but it's fiddly: you must merge child ranges, guard empty subtrees, and get the comparison direction right at every join. The top-down bound-passing version expresses the same invariant with far less to get wrong; reach for it first.false the moment the current value isn't strictly greater than the previous one. It's O(n) time and lets you bail early on the first out-of-order pair; the only state you carry is one prev variable instead of a pair of bounds.n deep). Convert it to a loop by pushing [node, low, high] triples onto an explicit array-stack and processing them yourself — same logic, same bounds, but the depth lives in heap memory you control instead of the JS engine's call stack.BSTIterator class that exposes next()/hasNext() over the in-order sequence, holding only the path of "controlled-recursion" stack frames down to the current node (O(h) space). Validation then becomes "are successive next() values strictly increasing?", and the same iterator powers ordered traversal everywhere else.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.