Valid Binary Search Tree

You are given a binary tree represented in level-order. Your task is to determine whether the tree is a valid Binary Search Tree (BST). A BST is defined by the following properties:

(\textbf{For any node } x\text{, all nodes in the left subtree have values less than } x\text{'s value}) and (\textbf{all nodes in the right subtree have values greater than } x\text{'s value}). This property must hold for every node in the tree. An empty tree is considered a valid BST.

The tree is provided as a sequence of tokens in level-order where the keyword null indicates a missing node.

inputFormat

The input consists of two lines. The first line contains an integer (n) representing the number of nodes in the tree. The second line contains (n) tokens separated by spaces. Each token is either an integer or the string null (representing a missing node). For an empty tree, (n = 0).

outputFormat

Output a single line: True if the binary tree is a valid BST, otherwise False.## sample

7
3 9 20 null null 15 7

False