Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Preorder-Traversal-To-Tree-Using-Stack

Com­plete Code:


Out­put:

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

You may also like...