Iterative post order traversal of a Binary Search Tree using Stack in java

simpler version:

public void postOrders(Node root) {
Stack s = new Stack();
List visitedList = new ArrayList();
s.push(root);
while (!s.isEmpty()) {
Node n = (Node) s.peek();
if (((visitedList.contains(n.right) || n.right == null)
&& (visitedList.contains(n.left) || n.left == null))) {
Node node = (Node) s.pop();

System.out.print(node.data + " ");
visitedList.add(node);
/* removing already visited left and right nodes for space optimization*/
if(n.right!=null)
visitedList.remove(n.right);
if(n.left!=null)
visitedList.remove(n.left);

} else {
if (n.right != null) {
s.push(n.right);
}
if (n.left != null) {
s.push(n.left);
}
}

}
}


older version implementation:


import java.util.ArrayList;


public class BST_Impl {
BST_Node root=null;

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 10, 4, 0, 34, 23, -2,-2, 5, 12, 9, 15, };
BST_Impl tree = new BST_Impl();
for (int i = 0; i < arr.length; i++) {
tree.insert(new BST_Node(arr[i]));
}

System.out.println("postorder traversal using stack:");
tree.postorder_ByStack(tree.root);


}

public void postorder_ByStack(BST_Node root) {
Stack_BST_IMPL stack=new Stack_BST_IMPL();
ArrayList list=new ArrayList();
stack.push(new Stack_Node(root));  //pushing root to the stack
BST_Node pre=null;
while(!stack.isEmpty()) {
BST_Node curr=stack.peek().value;
if(pre==null||(pre!=null&&(pre.left==curr||pre.right==curr))) {  // the current node is whether root or children of a given previous node
if(curr.left!=null) {
stack.push(new Stack_Node(curr.left));
}else if(curr.right!=null) {
stack.push(new Stack_Node(curr.right));
}else {
stack.pop();
list.add(curr.value);
}
}else if(curr.left==pre) {  //ie left node of current node is already visited
if(curr.right!=null) {    // if there is right node of current node then push it on stack otherwise pop the current node itself.
stack.push(new Stack_Node(curr.right));
}else {
stack.pop();
list.add(curr.value);
}

}else if(curr.right==pre) {  // left and right node of current node is already visited, so its time to pop current node itself.
stack.pop();
list.add(curr.value);
}
pre=curr;
}
System.out.println(list);
}


public void insert(BST_Node node) {
BST_Node temp=root;
if(root==null) {
root=node;
}else {
while(temp!=null) {  //inserting as  leave of a node
if(temp.value>node.value) {
if(temp.left==null) {
temp.left=node;
break;
}
temp=temp.left;
}else if(temp.value
if(temp.right==null) {
temp.right=node;
break;
}
temp=temp.right;
}else {
System.out.println("cannot enter equal number:"+temp.value);
break;
}
}

}

}

}



class BST_Node{
BST_Node left;
BST_Node right;
int value;

public BST_Node( int value) {
this.value=value;
}

}

class Stack_Node{
BST_Node value;
Stack_Node next;

public Stack_Node(BST_Node value) {
this.value=value;
}


}

class Stack_BST_IMPL{
int size=0;
Stack_Node top=null;

void push(Stack_Node node) {
if(top==null) {
top=node;
}else {
node.next=top;
top=node;
}
size++;

}

public Stack_Node pop() {
Stack_Node temp;
temp=top;
if(top!=null) {
top=top.next;
temp.next=null;
size--;
}
return temp;

}

public Stack_Node peek() {
return top;
}

public boolean isEmpty() {
if(size==0) {
return true;
}

return false;
}


}