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


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.


  • 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:


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

You may also like...

  • naween0423

    Why cant we use a queue here then .. ???

  • lipsa patel

    On line 20 instead of “while(s1.isEmpty() == false)” you can use “while(!s1.isEmpty())“
    Same on line 35.

    line 36: should be System.out.print(s2.pop() + ” ”);

    line 52: The call should be i.preorderIteration(root);