A binary search tree (BST) is a binary tree where, for every node, all values in its left subtree are strictly smaller than the node's value and all values in its right subtree are strictly larger. This ordering is what makes searching a BST fast.
Given the root of a binary tree, return True if it is a valid BST and False otherwise. An empty tree is a valid BST. Duplicate values are not allowed.
Examples
2
/ \
1 3
Input: root = [2, 1, 3]
Output: True
5
/ \
1 4
/ \
3 6
Input: root = [5, 1, 4, None, None, 3, 6]
Output: False
Explanation: The root's right child is 4, but 4 < 5.
5
/ \
4 6
/ \
3 7
Input: root = [5, 4, 6, None, None, 3, 7]
Output: False
Explanation: Node 3 is in the right subtree of 5, so it must be greater than 5.
Constraints
0 <= number of nodes <= 1000-10**9 <= node.val <= 10**9
Goals
- State the BST invariant precisely (it applies to whole subtrees, not just direct children)
- Pass allowed bounds (low, high) down a recursion
- Alternatively, use the fact that an in-order traversal of a BST is strictly increasing