Given the root of a binary tree, decide whether it is a valid binary search tree: every node's LEFT subtree holds only values strictly smaller, its RIGHT subtree only values strictly larger, and both subtrees are themselves valid. Equal values are invalid.
Examples
Example 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Example 3:
Input: root = [5,4,6,null,null,3,7]
Output: false
Explanation: the 3 sits in 5's right subtree — checking only parent against child misses it.
Example 4:
Input: root = [2,2,2]
Output: false
Example 5:
Input: root = [1]
Output: true
Constraints
1 <= number of nodes <= 10^4
-2^31 <= Node.val <= 2^31 - 1
Prerequisites
Binary trees, and recursion over them: solve the children, combine, return. The base case is almost always the empty tree. Depth-first order (pre, in, post) and breadth-first by level — and knowing which one a problem is really asking for.
How to think about it
1. Carry the Bounds Down Optimal
Intuition
Checking each node against its own children is the classic wrong answer: a value can sit correctly under its parent and still violate an ancestor. What a node actually must satisfy is a RANGE inherited from every ancestor above it — going left tightens the upper bound to the parent's value, going right tightens the lower. Null bounds rather than integer sentinels, because the values span the whole int range.
Algorithm
1. The root may be anything: bounds are open on both sides. 2. A node must lie strictly inside its bounds. 3. Recurse left with the upper bound set to this node's value. 4. Recurse right with the lower bound set to this node's value.
Time & Space
Time O(n). Space O(h). An in-order walk that must come out strictly increasing is the same idea flattened.