Trees · 026Medium
Validate Binary Search Tree
Given the root of a binary tree, determine whether it is a valid binary search tree: every node in a left subtree is strictly less than the node, every node in a right subtree is strictly greater, and both subtrees are themselves valid BSTs.
Constraints
- The tree holds 1 to 10^4 nodes.
- -2^31 <= Node.val <= 2^31 - 1
- INPUT FORMAT
- `root` is a TreeNode object, not an array. The arrays in EXAMPLES are the level-order
- serialization the platforms print — breadth-first, with `null` for a missing child. The
- test runner builds a real tree from that array before calling your function.
Examples
isValidBST([2, 1, 3]) -> true isValidBST([5, 1, 4, null, null, 3, 6]) -> false // 3 sits left of 5 but under 4 isValidBST([1, 1]) -> false // equal values are not allowed isValidBST([1]) -> true // a single node is a valid BST isValidBST([1, null, 2, null, 3]) -> true // a right-skewed chain still qualifies isValidBST([-2147483648, null, 2147483647]) -> true // the 32-bit extremes are legal values
Edge cases
- Duplicate values make it invalid.
- Node values can reach the 32-bit limits.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — for each node scan its whole subtree for violations.
- Target
- O(n) time, O(h) space — carry a (min, max) bound down the recursion, or verify that an in-order traversal is strictly increasing.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/07-trees/026-validate-binary-search-tree.js ./practice c 026