Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST).
A valid BST is defined as:
- 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 the left and right subtrees must also be valid BSTs.
Input: root = [2,1,3]
Output: true
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- 1 <= Number of nodes <= 104
- -231 <= Node.val <= 231 - 1
Contents
- Approach 1 — Inorder Traversal (Brute Force)
- Approach 2 — Min/Max Range (Optimal)
- Complexity Analysis
Inorder Traversal
Inorder traversal of a BST produces a strictly increasing sequence.
Collect all values inorder and verify each is greater than the previous.
public boolean isValidBST(TreeNode root) {
List<Integer> inorder = new ArrayList<>();
inorderCollect(root, inorder);
for (int i = 1; i < inorder.size(); i++) {
if (inorder.get(i) <= inorder.get(i - 1)) return false;
}
return true;
}
private void inorderCollect(TreeNode node, List<Integer> list) {
if (node == null) return;
inorderCollect(node.left, list);
list.add(node.val);
inorderCollect(node.right, list);
}
Complexity:
- Time: O(n), Space: O(n) — stores all values.
Min/Max Range (Optimal, O(1) extra space)
Pass a valid range [min, max] down the recursion. At each node, verify its value is strictly
within the range; update the bounds for subtrees.
- For the left child: upper bound becomes node.val.
- For the right child: lower bound becomes node.val.
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 subtree: max = node.val
&& validate(node.right, node.val, max); // right subtree: min = node.val
}
Use Long.MIN_VALUE / Long.MAX_VALUE (not Integer) as initial bounds to handle nodes with values equal to Integer.MIN_VALUE or Integer.MAX_VALUE.
| Approach | Time | Space |
|---|
| Inorder traversal | O(n) | O(n) — list storage |
| Min/Max range | O(n) | O(h) — call stack only |