Validate Binary Search Tree

Given the root of a binary tree, return True if it is a valid binary search tree:

• every value in a node's left subtree is strictly less than the node's value,
• every value in its right subtree is strictly greater,
• and both subtrees are BSTs too.

Example 1

Input: root = [2, 1, 3]
Output: True

Example 2

Input: root = [5, 1, 4, None, None, 3, 6]
Output: False

4 is in 5's right subtree but is smaller than 5.

Example 3

Input: root = [5, 4, 6, None, None, 3, 7]
Output: False

3 < 6 is fine locally, but 3 sits right of 5.

Constraints

• 1 ≤ number of nodes ≤ 2 · 10^4
• -2^31 ≤ Node.val ≤ 2^31 - 1