Binary tree inorder, preorder, postorder iteratively traversal

in-order: left, parent, right
pre-order: parent, left, right
post-order: left, right parent

Comparatively, in-order traversal is easier to think through.

Simplified iteratively steps for in-order traversal:

1. Starting from  node A,  firstly looks for the left-most node (call it B) and print it, 
2. then print node B's parent,  
3. then the same process (step 1 and 2)  is applied to this parent node's right node.

The implementation of these steps are straight forward. 

Now lets think about the overall control of iterations. How to start? When to terminate?

Since the brute-force solution is recursion, intuitively we need to use stack to simulate the recursion function-call stack.

Initialization: push root node into stack;

Termination: when the stack is empty (every node get processed)

Here is the modification of each step:

1. Starting from a node (poped out from stack), push each non-left-most node into stack; print left-most node
2. pop out a node from stack (left-most-node's parent) and print out; 
3. keep poping while the node (which is just poped out from stack) does not have right node; If it has right node, push the right node into stack and start a new iteration.

code:
pre-order:
The idea is very similar. The major difference is:

• in-order: print node when poping the node out
• pre-order: print node before pushing to stack

Code:

post-order:

Post-order can be done utilizing pre-order. The observation is:

• pre-order: parent, left, right
• post-order: left, right, parent

If we modify pre-order traversal slightly, visiting right node first instead of left node, it will be:

• (right node first) pre-order: parent, right, left
• post-order: left, right, parent

post-order is the reverse of (right-node-first) pre-order.

Code: