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

Binary Tree-Postorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for pos­torder tra­ver­sal.

Tree Traversals - Postorder

Tree Tra­ver­sals — Postorder

Exam­ple:

Ear­lier we have seen “What is pos­torder tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will solve it with iterative/Non Recur­sive manner.

Approach:

  • We have seen how we do inorder and pre­order tra­ver­sals with­out recur­sion using Stack, But post order tra­ver­sal will be dif­fer­ent and slightly more com­plex than other two. Rea­son is post order is non-tail recur­sive ( The state­ments exe­cute after the recur­sive call).
  • If you just observe here, pos­torder tra­ver­sal is just reverse of pre­order tra­ver­sal (1 3 7 6 2 5 4 if we tra­verse the right node first and then left node.)
  • So idea is fol­low the same tech­nique as pre­order tra­ver­sal and instead of print­ing it push it to the another Stack so that they will come out in reverse order (LIFO).
  • At the end just pop all the items from the sec­ond Stack and print it.

Pseudo Code:

  1. Push root into Stack_One.
  2. while(Stack_One is not empty)
    1. Pop the node from Stack_One and push it into Stack_Two.
    2. Push the left and right child nodes of popped node into Stack_One.
  3. End Loop
  4. Pop out all the nodes from Stack_Two and print it.

See the ani­mated image below and code for more understanding.

 

Postorder traversal

Pos­torder traversal

Com­plete Code:


Out­put:

4 5 2 6 7 3 1
4 5 2 6 7 3 1

You may also like...