Rebuild a Search Tree From Its Node-First Listing
Implement bstFromPreorder
You are given the pre-order listing of a binary search tree with distinct values: each node appears before its left subtree, which appears before its right subtree. Rebuild the tree and return its root. A binary search tree is fully determined by its pre-order listing.
You can insert the values one at a time into an empty tree, which works because of the order they are listed in. A single left-to-right pass that carries an upper bound for each subtree does the same in linear time.
Example 1:
Input: preorder = [45,20,10,30,70,60,90]
Output: [45,20,70,10,30,60,90]
Example 2:
Input: preorder = [12,7,3,9,15,20]
Output: [12,7,15,3,9,null,20]
Example 3:
Input: preorder = []
Output: []
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ preorder.length ≤ 100; all values are distinct, 0 ≤ preorder[i] ≤ 1000 - ●
preorder is the pre-order listing (node, left subtree, right subtree) of some binary search tree (left subtree smaller, right subtree larger); such a tree is guaranteed to exist - ●
Return the root of that tree (checked as a level-order list); an empty listing gives the empty tree - ●
A tree is uniquely determined by its pre-order listing together with the search-tree property
preorder =