**Problem Statement:**

**Perform iterative post-order traversal on a binary tree using Single Stack.**

**Output:**

Post-order : 8 , 4 , 5 , 2 , 6 , 9 , 7 , 3 , 1

**Solution:**

**Download Source Code**

**By**

**post-order**traversal I mean , process the

**Left Node**,then

**Right Node**, and then

**Node**all this processing happens in Depth First Search fashion. I assume that you know the recursive way to iterate a binary tree.

**Pre-order Traversal**: Node, Left Node, Right Node -

**In-order Traversal :**Left Node, Node , Right Node - A+B

**Post-order Traversal:**Left Node, Right Node, Node - AB+

Iterative Traversal can also be done by Morris traversal , which uses the concept of Threaded Binary Trees.

Here we are performing iteration using a Single Stack, also refer to my post using two stacks.

Below is the algorithm and implementation of in-order traversal using Single Stack.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | /** * Iterative Pre-order traversal using single stacks */ public void iterativePostOrder(Node root) { Stack<Node> stack = new Stack<Node>(); Node curr = root; for (;;) { if (curr != null) { if (curr.right != null) stack.push(curr.right); stack.push(curr); curr = curr.left; } else { if (!stack.isEmpty()) { curr = stack.pop(); // odd case, exchange curr and top element if (!stack.isEmpty() && curr.right == stack.peek()) { stack.pop(); stack.push(curr); curr = curr.right; } else { System.out.print(curr+"\t"); curr=null; //move to right or null } } else break; } } } |

Please post your suggestions and comments

Happy Coding !!:)

My brother suggested I might like this website. He was entirely right.

ReplyDeleteThis post truly made my day. You can not imagine simply how much

time I had spent for this information! Thanks!

Feel free to visit my homepage :: chip munks