Validate Binary Search Tree
Problem
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both subtrees are also valid BSTs.
Examples
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.
Constraints
- •
The number of nodes is in the range [1, 10^4]. - •
-2^31 <= Node.val <= 2^31 - 1
Hints
Hint 1
A 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.
Hint 2
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.
Hint 3
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.
Solutions
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)