The problem
Given the root of a binary tree, decide whether it is a valid binary search tree: for every node, every value in its left subtree is strictly smaller, every value in its right subtree strictly larger, and both subtrees are themselves valid.
Examples
- Input
root = [2, 1, 3]
- Output
true
- Input
root = [5, 1, 4, null, null, 3, 6]
- Output
false
Constraints
- 1 ≤ number of nodes ≤ 10⁴
- −2³¹ ≤ Node.val ≤ 2³¹ − 1
The idea
Checking only that each child is on the correct side of its parent is not enough: in the tree [5, 4, 6, null, null, 3, 7], the 3 is correctly left of 6 but sits on 5’s right, where everything must be larger than 5.
So each node carries an allowed range, lo < value < hi, set by all its ancestors. The root may be anything. Going left, the node’s value becomes the new upper limit; going right, the new lower limit. The limits start beyond any possible value (a 64-bit number, or infinity), so the largest and smallest 32-bit values are still allowed.
- Time
- O(n)
- Space
- O(h)
Solution · every language run against every case
class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: # Every node must lie strictly between the bounds its ancestors set. def ok(node, lo, hi): if not node: return True if not lo < node.val < hi: return False return ok(node.left, lo, node.val) and ok(node.right, node.val, hi) return ok(root, float("-inf"), float("inf"))