Validate a BST

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7.

Return True if the tree is a valid BST: for every node, all values in the left subtree are strictly smaller and all values in the right subtree are strictly larger. This must hold for the whole subtree, not only for the direct children.

For [2, 1, 3] the answer is True; for [5, 1, 4, None, None, 3, 6] it is False (the 3 sits to the right of 5).

Examples

Example 1

Input:

is_valid_bst(root)  # root = [2, 1, 3]

Output:

True

Example 2

Input:

is_valid_bst(root)  # root = [5, 1, 4, None, None, 3, 6]

Output:

False

Constraints

• 0 <= number of nodes <= 100000
• The tree is not deeper than 800 levels.
• -10**9 <= val <= 10**9