Validate Binary Search Tree
MediumTrees
Given the root of a binary tree, return true if it is a valid binary search tree, and false otherwise.
In a valid one, for every node, all the values in its left subtree are smaller than the node’s value and all the values in its right subtree are larger. Equal values are not allowed on either side.
On this page a tree is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1.
Examples
Input: root = [10, 5, 15, 2, 7, 12, 20] Output: true
Everything left of 10 is smaller, everything right of it is larger, and the same holds at 5 and at 15.
Input: root = [10, 5, 15, null, null, 8, 20] Output: false
8 is a fine left child for 15, but it sits in the right subtree of 10 and is smaller than 10.
Constraints
- The tree has 1 to 10⁴ nodes.
-2³¹ ≤ node.val ≤ 2³¹ - 1
Stuck?
Hint 1
Comparing each node with its own two children is not enough: a value deep in the left subtree must be smaller than the root too, not just smaller than its parent.
Hint 2
Pass a range down as you recurse: each node must lie strictly between a lower and an upper bound. Going left, the node’s value becomes the upper bound; going right, it becomes the lower one. An in-order walk that must keep rising works as well.
The idea
Every node in a search tree has a range it must fall in, set by all of its ancestors, not only its parent. Going left lowers the top of the range to the parent's value, and going right raises the bottom. Check each node against the range it inherits.
Time O(n)Extra space O(h) for a tree of height h
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
within checks that every value in a subtree lies strictly between low and high. An empty subtree has nothing that could break the rule.
function isValidBST(root) { const within = (node, low, high) => { if (!node) return true; if (node.val <= low || node.val >= high) return false; return within(node.left, low, node.val) && within(node.right, node.val, high); }; return within(root, -Infinity, Infinity);}The trap
Checking each node only against its own two children catches a child on the wrong side of its parent, the mistake you picture first. It misses a value deeper down that is on the right side of its parent but the wrong side of a grandparent or the root. A tree like that passes every local check and is still not a search tree.
function isValidBST(root) { if (!root) return true; // checks each node against its own children only 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);}