Postorder Iteration with Two Stacks
1. Postorder Recursion
//postorder recursion
public static void PostOrder(Node r) {
if( r != null) {
PostOrder(r.left);
PostOrder(r.right);
System.out.println("[" + r.data + "]");
}
}

1. Postorder with Two Stacks
2. Level order using two queues
//Postorder with two stacks
public static void PostorderTwoStacks(Node curr) {
Stack<Node> st1 = new Stack<Node>();
Stack<Node> st2 = new Stack<Node>();
if(curr != null) {
st1.push(curr);
while(!st1.empty()) {
Node node = st1.pop();
st2.push(node);
if(node.left != null)
st1.push(node.left);
if(node.right != null)
st1.push(node.right);
}
while(!st2.empty()) {
Node node = st2.pop();
System.out.println("Two Stacks Iteration["+node.data+"]");
}
}
}


1. Postorder with Iteration
// postorder with iteration
public static void postIteration(Node root) {
Stack<Node> stack = new Stack<Node>();
Node curr = root;
while(curr != null || stack.isEmpty() == false) {
if(curr != null) {
stack.push(curr);
curr = curr.left;
} else {
Node node = stack.peek();
if(node.isVisited) {
System.out.println("[" + node.data + "]");
stack.pop();
} else {
node.isVisited = true;
curr = node.right;
}
}
}
}

1. Inorder and Inorder Iteration
public static void preorder(Node root) {
if(root != null) {
System.out.println("[" + root.data + "]");
inorder(root.left);
inorder(root.right);
}
}
public static void inorder(Node root) {
if(root != null) {
inorder(root.left);
System.out.println("[" + root.data + "]");
inorder(root.right);
}
}

public static void preorderIteration(Node r) {
Stack<Node> st = new Stack<Node>();
Node curr = r;
if( curr != null) {
while(curr != null || !st.empty()) {
if(curr != null) {
System.out.println("["+curr.data+"]");
st.push(curr);
curr = curr.left;
} else {
Node node = st.pop();
curr = node.right;
}
}
}
curr = r;
}

public static void inorderIteration(Node r) {
Stack<Node> st = new Stack<Node>();
Node curr = r;
if( curr != null) {
while(curr != null || !st.empty()) {
if(curr != null) {
st.push(curr);
curr = curr.left;
} else {
Node node = st.pop();
System.out.println("["+curr.data+"]");
curr = node.right;
}
}
}
curr = r;
}

Implement Iterator with inorder traversal
class InorderIterator {
Node curr;
Stack<Node> stack = new Stack<Node>();
public InorderIterator(Node r) {
this.curr = r;
}
public boolean hasNext() {
if(curr != null || stack.size() > 0)
return true;
else
return false;
}
public int next() {
while(hasNext()) {
if(curr != null) {
stack.push(curr);
curr = curr.left;
} else {
Node node = stack.pop();
curr = node.right;
return node.data;
}
}
return -1;
}
}