Description
Given an array of integers preorder representing the preorder traversal of a BST, construct the tree and return its root.
Examples
Input:
preorder = [8,5,1,7,10,12]Output:
[8,5,10,1,7,null,12]Explanation:
BST constructed.
Input:
preorder = [4,2,1,3,6,5,7]Output:
[4,2,6,1,3,5,7]Explanation:
This is a balanced BST case. Starting with root 4, adding 2 (left child), then 1 (left of 2), then 3 (right of 2). Next, 6 becomes right child of 4, followed by 5 (left of 6) and 7 (right of 6). The output shows level-order traversal of the constructed BST.
Input:
preorder = [10,5,3,8,15]Output:
[10,5,15,3,8,null,null]Explanation:
This demonstrates a partially skewed BST. Root is 10, then 5 goes left, 3 goes left of 5, 8 goes right of 5, and 15 goes right of root 10. The resulting tree has more nodes on the left subtree, showing how preorder traversal can create unbalanced but valid BSTs.
Constraints
- •
1 ≤ preorder.length ≤ 100