# [Question] Construct a BST From Preorder Traversal

### 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(n2) 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;
}
``````