Check if Binary Tree is a Binary Search Tree

You are given a binary tree in the form of a level order traversal. Your task is to determine whether the given tree is a valid Binary Search Tree (BST). A BST is defined so that for every node with value \(v\), all nodes in its left subtree have values less than \(v\) and all nodes in its right subtree have values greater than \(v\). Formally, for every node, if the value is \(v\), then for every node in the left subtree, it must hold that \(low < v_node < v\), and for every node in the right subtree, \(v < v_node < high\), where the bounds update accordingly.

The level order input will be provided using an array notation with missing nodes represented as null. For example, the tree:

    4
   / \
  2   5
 / \
1   3

will be represented as [4,2,5,1,3].

Use the model solution approach with recursion and bounds checking to solve this.

inputFormat

Input Format: The input is given as a single line from stdin consisting of a string that represents the level order traversal of the binary tree. The tree is represented in array notation, e.g., [4,2,5,1,3] for a non-empty tree or [] for an empty tree. In the array, missing nodes are denoted by null (without quotes).

outputFormat

Output Format: Print a single line to stdout that is either True if the binary tree is a valid BST, or False otherwise.

[]

True