Trees: Iterative Post-order traversal using Single Stack

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   -  +AB
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 !!:)