Validate Binary Search Tree
Problem
Decide whether a binary tree is a valid binary search tree: every value in a node's left subtree must be strictly smaller than it and every value in its right subtree strictly larger, recursively.
Examples
Constraints
- • 1 <= number of nodes <= 10^4
- • -2^31 <= Node.val <= 2^31 - 1
Hints & approach
Hint 1
Checking each node only against its direct children is not enough.
Hint 2
Every node must fall inside an open range inherited from its ancestors.
Hint 3
Going left tightens the upper bound; going right tightens the lower bound.
Approachtry the hints first
Recurse with a (low, high) range, starting from (-infinity, +infinity). A node is valid if low < val < high and its left subtree is valid in (low, val) and its right subtree is valid in (val, high). An equivalent check is that an inorder traversal produces a strictly increasing sequence, which you can verify by tracking the previous value.
Time O(n) · Space O(h)