Construct Binary Search Tree from Preorder Traversal

You are given a list of distinct integers representing the preorder traversal of a binary search tree (BST). Your task is to construct the BST following these rules:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both left and right subtrees must also be valid BSTs.

The BST is constructed by inserting the values in the given order from the preorder traversal. Once the tree is built, perform a level order traversal and output the tree as a list (in Python list format). For missing nodes, output None in their place. Use LaTeX for any formulas if needed; for example, the BST properties can be written as: \( \text{if } v \text{ is a node, then } \forall u \in \text{left subtree of } v,\; u v. \)

The input will be read from standard input. The output should be printed to standard output.

inputFormat

The input is provided via standard input as a single line containing space-separated integers. If the line is empty, it represents an empty list. For example:

8 5 1 7 10 12

represents the preorder traversal [8, 5, 1, 7, 10, 12].

outputFormat

Output the level order traversal of the constructed BST in a list format. The output should be exactly in the Python list style, where missing nodes are represented by None. For the above input, the output should be:

[8, 5, 10, 1, 7, None, 12]

## sample

8 5 1 7 10 12

[8, 5, 10, 1, 7, None, 12]