### Question

Given preorder, construct the BST.

### Solution

We can get **Inorder traversal** by sorting the given Preorder traversal. So we have the required two traversals to construct the Binary Search Tree.

A very similar approach would be **always spliting the array** by the head value. Time complexity is O(nlgn) for a balanced BST, or O(n^{2}) for a screwed tree.

**Howver, there’s O(n) solutions**.

The trick is to set a range {min .. max} for every node. Initialize the range as {INT_MIN .. INT_MAX}. The first node will definitely be in range, so create root node. To construct the left subtree, set the range as {INT_MIN â€¦root->data}. If a values is in the range {INT_MIN .. root->data}, the values is part part of left subtree. To construct the right subtree, set the range as {root->data..max .. INT_MAX}.

**The key** is the we need **a public variable** as a pointer (to traverse thru the array).

There’s another O(n) solution using stack. I wont' cover for now.

### Code

**written by me**

It’s not an easy question, to be frank.

```
int p;
public TreeNode solution(int[] preorder) {
p = 0;
return helper(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode helper(int[] A, int min, int max) {
int len = A.length;
if (p >= len) {
return null;
} else if (A[p] < min || A[p] > max) {
return null;
}
TreeNode root = new TreeNode(A[p]);
p++;
root.left = helper(A, min, root.val);
root.right = helper(A, root.val, max);
return root;
}
```