# Construct Binary Search Tree from a given Preorder Traversal using Recursion

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 val­i­date the right child of 30, it can take any value between 30 and + ∞. When you val­i­date the left child of 30, it can take any value between — ∞ and 30. likewise

So the idea is Pass the min­i­mum and max­i­mum val­ues 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 min­i­mum = Integer.MIN_VALUE and max­i­mum = 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 min­i­mum = Integer.MIN_VALUE and max­i­mum = 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 fig­ure for bet­ter understanding. ( 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; } }

view raw
PreorderToTree.java
hosted with ❤ by GitHub

Output:

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