98. Validate Binary Search Tree
Your function receives root, the root node of a binary tree (each node has an integer val plus left and right child pointers). Return true if the tree obeys the binary search tree ordering rule, and false otherwise.
The rule is global, not just parent-to-child: for every node, every value anywhere in its left subtree must be strictly smaller than the node's value, and every value anywhere in its right subtree must be strictly greater. Equal values are not allowed.
The classic trap: checking only each parent against its two children accepts trees that are locally ordered but globally broken — a grandchild can sneak outside the range its ancestors allow (see the figure).
Example 1:
Input: root = [2, 1, 3]
Output: true
Explanation: 1 < 2 in the left subtree and 3 > 2 in the right subtree — the ordering rule holds at every node.
Example 2:
Input: root = [5, 1, 4, null, null, 3, 6]
Output: false
Explanation: The right child 4 is already smaller than the root 5, so the tree fails immediately (its subtree values 3 and 6 make it worse).
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -2³¹ ≤ node value ≤ 2³¹ - 1
Hints:
Comparing each node only with its direct children is not enough — a node deep in the right subtree must still exceed every ancestor it descended left of. Think about what *range* of values each position is allowed to hold.
Two clean fixes: (a) an inorder traversal of a valid BST visits values in strictly increasing order, so walk inorder and compare each value with the previous one; (b) recurse with an allowed open interval (lo, hi), tightening one bound at each step.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [2, 1, 3]
Expected output: true