Construct BST from Preorder
mediumTrees & BST II+20 XPTime limit 2s
You are given the preorder traversal (node, then left subtree, then right subtree) of a binary search tree with distinct values. Rebuild the tree and print it.
For a BST, the preorder alone is enough: the first value is the root, the smaller values that follow form the left subtree, and the rest form the right subtree.
Input:
- line 1:
n— the number of nodes - line 2: the preorder sequence (it always comes from a real BST)
Output: the tree in level order (top to bottom, left to right) with null for a missing child and trailing nulls left out — e.g. 3 9 20 null null 15 7; an empty tree is null.
Constraints: 1 ≤ n ≤ 10⁴, distinct values between −10⁵ and 10⁵. The tree's height is at most 500.
Think about it: inserting the values one by one into an empty BST gives the right tree, but costs O(n·h). The O(n) way: read the sequence once with a recursive build(upperBound) — the next value becomes a node only if it is below the bound; its left subtree gets the node's value as the new bound, its right subtree keeps the old bound.
Sample input 1
6 8 5 1 7 10 12
Sample output 1
8 5 10 1 7 null 12
Sample input 2
2 1 3
Sample output 2
1 null 3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).