**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
and**minimum = Integer.MIN_VALUE**, so your root can take any value between this range.**maximum = Interger.MAX_VALUE** - So when putting the left node of 20(root), it must lie within the range to
, so check the next element in the**minimum = Integer.MIN_VALUE and maximum = 20**, 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. (**preorder[]**)**see the execution sequence** - Solve it recursively.

**Time Complexity: O(n)**

**Complete Code:**

public class PreorderToTree { | |

public int pIndex = 0; | |

public Node constructTree(int[] preorder, int data, int min, int max) { | |

if (pIndex < preorder.length) { | |

if (preorder[pIndex] > min && preorder[pIndex] < max) { | |

Node root = new Node(data); | |

pIndex++; | |

if (pIndex < preorder.length) { | |

// nodes lies between min and data will create left subtree | |

root.left = constructTree(preorder, preorder[pIndex], min, | |

data); | |

// nodes lies between data and max will create right subtree | |

root.right = constructTree(preorder, preorder[pIndex], | |

data, max); | |

} | |

return root; | |

} | |

} | |

return null; | |

} | |

public void displayTree(Node root) { | |

if (root != null) { | |

displayTree(root.left); | |

System.out.print(" " + root.data); | |

displayTree(root.right); | |

} | |

} | |

public static void main(String args[]) { | |

PreorderToTree p = new PreorderToTree(); | |

int[] preOrder = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 }; | |

Node root = p.constructTree(preOrder, preOrder[0], Integer.MIN_VALUE, | |

Integer.MAX_VALUE); | |

System.out.println("Inorder Traversal of Constructed Tree : "); | |

p.displayTree(root); | |

} | |

} | |

class Node { | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

} | |

} |

**Output**:

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