Given the root of a binary tree, determine if it is a valid binary search tree.
For every node, all values in the left subtree must be smaller and all values in the right subtree must be greater.
Reason about the value returned from each subtree and the state passed down from ancestors. Empty children and single-node trees should be handled naturally.
Examples
Input: root = [2,1,3] Output: true
Input: root = [5,1,4,null,null,3,6] Output: false
Constraints
- The number of nodes in the tree is in the range [1, 10,000].
- -2^31 <= Node.val <= 2^31 - 1