# 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 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.

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...

• 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);