Validate Binary Search Tree

You get the root of a binary tree. Return True if it is a valid binary search tree (BST). Otherwise, return False.

The tree is a valid BST when this holds at every node:

• every value in its left subtree is strictly smaller than the node,
• every value in its right subtree is strictly larger.

This covers whole subtrees, not just the two children. Each value must follow the rule for every node above it.

The trees below are listed level by level, top to bottom and left to right. A missing child is written as None.

Example 1:

      8
     / \
    3   12
   / \
  1   5

Input: root = [8,3,12,1,5]
Output: True
Explanation: 3, 1 and 5 are all smaller than 8.
12 is larger than 8.
Under 3, 1 is smaller and 5 is larger.

Example 2:

      8
     / \
    3   12
   / \
  1   9

Input: root = [8,3,12,1,9]
Output: False
Explanation: 9 is larger than 3, so it fits as the right child of 3.
But 9 is also in the left subtree of 8.
There, every value must be smaller than 8.

Example 3:

  6
   \
    6

Input: root = [6,None,6]
Output: False
Explanation: The right child is equal to the root.
The right side needs strictly larger values.

Constraints:

• 1 to 10,000 nodes.
• Each value is a 32-bit signed integer, from -231 to 231 - 1.
• The tree is at most 800 levels deep.