Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

binary search tree is a binary tree where for every node, any descendant of `Node.left` has a value strictly less than `Node.val`, and any descendant of `Node.right` has a value strictly greater than `Node.val`.

preorder traversal of a binary tree displays the value of the node first, then traverses `Node.left`, then traverses `Node.right`.

Example 1:

```Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
```

Example 2:

```Input: preorder = [1,3]
Output: [1,null,3]
```

Constraints:

• `1 <= preorder.length <= 100`
• `1 <= preorder[i] <= 108`
• All the values of `preorder` are unique.

## Efficient Solutions by OpHaxor:

```public TreeNode bstFromPreorder(int[] pre) {
return construct(pre,0,pre.length-1);
}

private static TreeNode construct(int pre[],int start,int end) {
if(start>end) {
return null;
}

TreeNode root=new TreeNode(pre[start]);

for(int i=start+1;i<=end;i++) {
if(pre[i]>root.val)
break;
}

root.left=construct(pre,start+1,i-1);
root.right=construct(pre,i,end);

//return the root
return root;
}```
```def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
def insert(head,val):
prev = head
while head:
prev = head
if val<head.val:
head = head.left
else:
head = head.right

if val<prev.val:
prev.left = TreeNode(val)
else:
prev.right = TreeNode(val)

head = TreeNode(preorder[0])

for i in range(1,len(preorder)):
node = preorder[i]
insert(head,node)

return head

```
```public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
return helper(preorder, 0, INT_MAX).first;
}

pair<TreeNode*, int> helper(vector<int>& nums, int start, int bound) {
if (start == nums.size() || (nums[start] >= bound))
return {NULL, start};
TreeNode* root = new TreeNode(nums[start]);
auto l = helper(nums, start+1, root->val);
root->left = l.first;
auto r = helper(nums, l.second, bound);
root->right = r.first;
return {root, r.second};
}```
Previous Post

Next article