Valid Binary Search Tree

A binary search tree keeps its values in order: for every node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger. Write is_valid_bst(root) that returns True if the tree follows this rule at every node, and False otherwise. Equal values are not allowed, and an empty tree is valid.

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

    8
   / \
  4   10
     /  \
    6    12

is_valid_bst(build([6, 2, 9]))  # returns True
is_valid_bst(build([7, 3, 5]))  # returns False
is_valid_bst(build([8, 4, 10, None, None, 6, 12]))  # returns False

In the second tree the right child 5 is smaller than the root 7. The drawing shows the third tree, where each node looks fine next to its own children: 6 is smaller than its parent 10. But 6 sits in the right subtree of the root 8, where every value must be larger than 8.

Constraints

• 0 to 2,000 nodes; values are integers from -1,000,000,000 to 1,000,000,000.