Construct a BST from Preorder Traversal
Build a binary search tree from a given preorder traversal sequence.
Input format
The first line contains N. The second line contains the preorder traversal of a valid BST.
Output format
Construct the BST from the preorder traversal. Print level-order of the result.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
13
26 16 4 8 78 63 60 59 40 94 87 81 79Expected output
26 16 78 4 63 94 8 60 87 59 81 40 79Example 2
Input
6
40 18 9 17 63 48Expected output
40 18 63 9 48 17