**Objective:** **– **Given a preorder traversal, construct BST from that.

**Input:** Preorder traversal

**Similar Problem** : This problem is similar to the – Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion)

**Approach: **

Solution to the problem is similar to *isBST Max-Min Solution.*

*“Your root value can have any value between -∞ to + ∞, say it is 30 here, When you validate the right child of 30, it can take any value between 30 and + ∞. When you validate the left child of 30, it can take any value between — ∞ and 30. likewise *

So the idea is *Pass the minimum and maximum values between which the node’s value must lie*.

- Example:
** int[] preOrder = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 }**;
- First element in the preorder[] will definitely be the root, which is 20 here.
- we start with the range
** minimum = Integer.MIN_VALUE** and **maximum = Interger.MAX_VALUE**, so your root can take any value between this range.
- So when putting the left node of 20(root), it must lie within the range to
**minimum = Integer.MIN_VALUE and maximum = 20**, so check the next element in the **preorder[]**, if it lies in this range, make it the left child to the root, else it must the the right chlid of the root and so on. See the figure for better understanding. ( **see the execution sequence**)
- Solve it recursively.

**Time Complexity: O(n)**

**Complete Code:**

**Output**:

Inorder Traversal of Constructed Tree :
1 5 7 10 15 20 25 30 32 35 40

__________________________________________________

**Top Companies Interview Questions..-**

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

__________________________________________________

### Like this:

Like Loading...

*Related*