CareerCup

two stack solution will work with lil modification

1. Initially push the root into stack1.
2. while stack1 is not empty pop one element from stack1 and push into stack2 and push its left and right child into stack1
3. pop elements in stack2 will give the postorder

A
        /   \
       B     C
      / \   /
     D   E F

     stack1	       stack2
	A		empty		 	
	BC		A
	BF		AC
	B		ACF
	DE		ACFB
	D		ACFBE
	empty		ACFBE

pop stack2 EBFCA -> postorder

//Using Two Stack

void postorder_traverse(struct tree *root)
{
	struct tree *stack1[10],*stack2[10];
	int top1=-1,top2=-1,t;
	while(1)
	{
		while(root)
		{
			push(stack1,root,&top1);
			push(stack2,root,&top2);
			root=root->left;
						
		}
		if(top1==-1 && top2==-1)
			break;
		if(stack1[top1]==stack2[top2])
		{
	
			root = pop(stack1,&top1);		
			root=root->right;
		}
		else
		{
			root = pop(stack2,&top2);
			printf("\t %d ",root->data);
			root=NULL;
		}
	}
}

I guess we can do a depth first search( marking the postvisit numbers for each node ). Now sort the nodes according to the postvisit number. This is the requires postorder traversal.

you need to use two stacks for this problem

Do a depth first search iteratively using stack1 and while adding elements to stack1, add them to stack2 as well. Once the iteration is over, all elements in post-order are in stack 2.

How thw stack2 will have elements in post order. After the 1st level the order in stack 2 is root, right left. Now the left will be poped and it's child will be pushed. Followed by right.
So if you have a tree with depth more than one the stack2 will not be in postorder.

What Metta means is this (appears working to me):

Stack S, R;
S.push(head);
R.push(head);
while (S is not empty) {
n = S.pop();
if (n.right) { S.push(n.right); R.push(n.right); }
if (n.left) { S.push(n.left); R.push(n.left); }
}
print(R);

sorry - above solution given by Schultz is not correct.

Only one stack will do. Will use 3 special nodes RIGHT , LEFT and NULL also: RIGHT node means now move to right subtree, LEFT node means, now move to left subtree and NULL means, print the node.

void postOrder(Node root)
{
Node node, val;
Stack S;
S.push(RIGHT);
S.push(root);

while(!S.empty()
{
node = S.pop();
val = S.pop();
if(val == RIGHT)
{
if(node.right)
{
S.push(LEFT);
S.push(node);
S.push(RIGHT);
S.push(node.right);
}
else if(node.LEFT)
{
S.push(NULL);
S.push(node);
S.push(RIGHT);
S.push(node.LEFT);
}
else
print node;
}
else if(val == LEFT)
{
if(node.left)
{
S.push(NULL);
S.push(node);
S.push(RIGHT);
S.push(node.left);
}
}
else
print node;
}
}

#define LEFT 0
#define RIGHT 1
#define NONE 3

typedef struct binTreeNode{
int val;
int visited;
struct binTree* left;
struct binTree* right;
} nodeType;

postOrderTraversal(nodeType* node){
if ( node == NULL ){
return NULL;
}

while ( node != NULL ){
node->visited = LEFT;
push(node);
node = node->left;

}

while ( (node = pop()) != NULL ){
if (( node->visited == LEFT ) &&
( node->right != NULL )){
node->visited = RIGHT;
push(node);
node = node->right;
while ( node != NULL ){
node->visited = LEFT;
push(node);
node = node->left;
}
}
else{
node->visited = NONE;
printf("%d\n", node->val);
}
}
}

small mistak in the prev post. i forgot to append D in the last step

A trick to make things with a single stack it self.

1. Push all the left nodes till you encounter null.

while(stack is not empty)
pop the first element.

if popped element is dummy (I 'll explain the logic behind this), then pop the next
element and print it out.

if the popped element does not have a right child, print it out

if the popped element has a right child
then
a) push the popped element, and a dummy node. This dummy node indicates that we
should print whatever node that sits below this node on stack, which would be the prior pushed node. This is to indicate that a node has a right child and should only be printed (and not re-evaluated for the presence of right tree) when later that node is encountered on the stack.

b) push the right child
b) push all the element to the left of this right child.

end while

And the code:
public void postOrderTraversal(Node node) {
if (node == null) {
return;
}

Node dummy = new Node();

LinkedList<Node> list = new LinkedList<Node>();
list.add(node);

while (node.left != null) {
list.add(node.left);
node = node.left;
}

while (!list.isEmpty()) {

Node popped = list.removeLast();

if (popped == dummy) {
System.out.println(list.removeLast().data);
} else if (popped.right == null) {
System.out.println(popped.data);
} else {
list.add(popped);
list.add(dummy);
Node rightTree = popped.right;

list.add(rightTree);

while (rightTree.left != null) {
list.add(rightTree.left);
rightTree = rightTree.left;
}

}
}
}

public void printPostOrderNR() {
BinarayTreeNode node = root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
if(node != null)
stack.push(node);

while (stack.isempty() == false){
node = stack.peek();
if(node.getVisited()) {
stack.pop();
node.print();
}
else {
node.setVisited();
right = node.getRight();
if(right != null) stack.push(right);
left = node.getLeft();
if(left != null) stack.push(left);
}
}

struct{
       mynode *node;
       unsigned vleft :1;   // Visited left?
       unsigned vright :1; // Visited right?
}save[100];

  / Iterative Postorder
void iterativePostorder(mynode *root)
{
   
   int top = 0;
   save[top++].node = root;
   while ( top != 0 )
   {
         /* Move to the left subtree if present and not visited */
         if(root->left != NULL && !save[top].vleft)
         {
             save[top].vleft = 1;
             save[top++].node = root;
             root = root->left;
             continue;
         }
         /* Move to the right subtree if present and not visited */
         if(root->right != NULL && !save[top].vright )
         {
             save[top].vright = 1;
             save[top++].node = root;
             root = root->right;
             continue;
         }
         printf("[%d] ", root->value);
         /* Clean up the stack */
         save[top].vleft = 0;
         save[top].vright = 0;
         /* Move up */
         root = save[--top].node;
     }
}

silly mistake: the struct should be like this,

struct{
       mynode *node;
       unsigned vleft  :0;   // Visited left?
       unsigned vright :0; // Visited right?
}save[100];

flag 0: not visited, the default value
flag 1: visited, changed after visiting the node

void PostOrder(node *root)
    {
        Stack s1, s2;
        s1.push(root);
        while(!s1.isEmpty())
        {
            Node n = s1.pop();
            Node left = n->left;
            Node right = n->right;
            s2.push(n);
            s1.push(left);
            s1.push(right);
        }

        while(!s2.isEmpty())
        {
            printf("%d", s2.pop());
        }
    }