# Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion)

Objec­tive: - Given a pre­order tra­ver­sal, con­struct BST from that, with­out using recursion.

Input: Pre­order traversal

Sim­i­lar Prob­lem : This prob­lem is sim­i­lar to the Con­struct Binary Search Tree from a given Pre­order Tra­ver­sal using Recur­sion.

Approach:

• Exam­ple: int[] pre­Order = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 };
• Use Stack.
• First ele­ment in the pre­order[] will def­i­nitely be the root, which is 20 here.
• Cre­ate a node with data 20 and push it in Stack.
• Now take the next ele­ment (say ‘data’) from the pre­order sequence.
• If ‘data’ is greater than the top item in the stack then keep pop­ping out the nodes from the stack, keep stor­ing it in temp node till the top node in stack is less than the ‘data’.
• cre­ate a node with ‘data’ and add it to the right of temp node and push the temp node to stack.
• If ‘data’ is less than the top item in the stack then cre­ate a node with ‘data’ and add it to the left of top node in stack and push it in the stack.
• Repeat the above two steps till all the ele­ments in pre­order[] is over.
• return the root

Time Com­plex­ity: O(n)

Preorder-Traversal-To-Tree-Using-Stack

Com­plete Code:

Out­put:

```Inorder Traversal of Constructed Tree :
2 5 7 10 12 15 20```