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

Objective: - Given a preorder traversal, construct BST from that, without using recursion.

Input: Preorder traversal

Similar Problem : This problem is similar to the Construct Binary Search Tree from a given Preorder Traversal using Recursion.

Approach:

Example: int[] preOrder = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 };
Use Stack.
First element in the preorder[] will definitely be the root, which is 20 here.
Create a node with data 20 and push it in Stack.
Now take the next element (say 'data') from the preorder sequence.
If 'data' is greater than the top item in the stack then keep popping out the nodes from the stack, keep storing it in temp node till the top node in stack is less than the 'data'.
create 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 create 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 elements in preorder[] is over.
return the root

Time Complexity: O(n)

Output:

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