Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST:
Example 1
Input: root = [2,1,3]
Output: true
Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: Root is 5 but right child is 4 < 5.
The number of nodes is in the range [1, 10^4].-2^31 <= Node.val <= 2^31 - 1A common WRONG approach: checking only that each node's immediate children satisfy the local BST comparison. This misses violations further down — a node can be locally correct relative to its parent but still violate the global ordering relative to a grandparent.
Pass min and max bounds down the recursion — each node must be within its valid range, which correctly captures the GLOBAL constraint, not just a local one.
An inorder traversal of a valid BST must produce strictly increasing values — checking that directly is a simpler, if less elegant, alternative to bounds-passing.
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) // left must be < node.val
&& validate(node.right, node.val, max); // right must be > node.val
}Time: O(n) · Space: O(h)