CareerCup

This code is easy to remember because it is similar in structure to the recursive version. Uses a single stack with bool flag embedded in node to track state of node.

Simple, neat and petite.

template<class T>
struct Node {
    Node(T _data) : item(false),data(_data), 
	                left(0), right(0){}
    Node() : item(false),data(), left(0), right(0){}
    Node*   asItem() { item=true; return this;}
    Node*   asLink() { item=false; return this;}
    bool    isItem() const {return item; }
    bool item; T data; Node* left; Node* right;
}; 
typedef Node<int> Tree;
   
void postOrderIterative(Tree* root) {
    if(!root) return;
    
    std::stack<Tree*> s; s.push( root->asLink() );
    
    while( !s.empty() ) {
    
        root = s.top(),s.pop();
        if( root->isItem() ) {
            
            std::cout << root->data << std::endl;
    
        } else {
    
            s.push( root->asItem() );
            if( root->right ) s.push(root->right->asLink());
            if( root->left )  s.push(root->left->asLink());
        }
    }
}

1. Use a stack to simulate recursion of function. And user a flag to check if the subtree is checked.

#include <iostream>
using namespace std;

#define LEFT_SUB_TREE_TRANS 1
#define RIGHT_SUB_TREE_TRANS 2
#define MAX_STACK_SIZE 1000

struct btree
{
	struct btree * left; 
	int * data;
	struct btree * right;
};

struct stack_node
{
	struct btree * node;
	int flag;
};


void poster_order(struct btree * bt1)
{
	if(NULL == bt1) return;
    stack_node stack[MAX_STACK_SIZE];
	int top = 0;
	struct btree * p = bt1;
	while(p) {stack[top].flag = LEFT_SUB_TREE_TRANS; stack[top++].node = p; p = p->left;}
	while(top)
	{
		if(stack[top-1].flag == RIGHT_SUB_TREE_TRANS) { cout<<*(stack[top-1].node->data)<<endl; top --; }
		else
		{
			stack[top-1].flag = RIGHT_SUB_TREE_TRANS;
			p = stack[top-1].node->right;
			while(p) {stack[top].flag = LEFT_SUB_TREE_TRANS; stack[top++].node = p; p = p->left;}			
		}
		
	}

}

u can use this one which i think the simplest way to do postorder iteratively
void PostOrder(struct node *T)
{
struct node *temp=T;
stack *s1=NULL,*s2=NULL;
if(temp==NULL)
return;
Push(temp,s1);
while(!isEmpty(s1))
{
temp=Pop(s1);
Push(temp,s2);
if(temp->left)
Push(temp->left,s1);
if(temp->right)
Push(temp->right,s2);
}
while(!isEmpty(s2))
printf("%d",(Pop(s2))->data);
}

thanks for finding the mistake in code :)

Is this correct?

void PostOrder(TreeNode* root)
{
	TreeNode* current=root;
	TreeNode* n;
	stack<TreeNode*> mystack;
	mystack.Push(current);
		while(true)
		{
			if(current==NULL) break;
			n = current->right;
			if(n!=NULL)
				mystack.Push(n);
			n = current->left;
			if(n!=NULL)
				mystack.Push(n);
			cout<<current->info;
				current=mystack.Top();
				myStack.Pop();
		}
	}
}

void postorder(btree *p)
{
        stack<btree*> stk1, stk2;
        if(p == 0)
                return;

        stk1.push(p);
        while(!stk1.empty())
        {
                p = stk1.top();
                stk2.push(p);
                stk1.pop();
                if(p->left)
                        stk1.push(p->left);
                if(p->right)
                        stk1.push(p->right);
        }

        while(!stk2.empty())
        {
                cout << stk2.top()->data << "   ";
                stk2.pop();
        }
        cout << endl;
}

PO()
	s.push(root)
        l.push(0)
        r.push(0)
	n = root
	if(s.isNotEmpty())
		if(!l.top() && n)
			l.top() = 1
			s.push(n->left)
			n = n->left
			l .push(0)
		else if(!r.top() && n)
			r.top() = 1
			s.push(n->right)
			n = n->r
			r.push(1)
		else if(n)
			print n->data
			n = s.pop()
			l.pop()
			r.pop()
		else
			print s.pop()->data
			n = s.pop()
			l.pop()
			r.pop()

<T> List<T> postOrderIter(TreeNode<T> node) {
    List<T> l = new ArrayList<>();
    Stack<Pair<TreeNode<T>, Boolean>> s = new Stack<>();
    s.push(new Pair<TreeNode<T>, Boolean>(node, false));
    while (!s.empty()) {
      Pair<TreeNode<T>, Boolean> p = s.pop();
      if (p.snd) {
        l.add(p.fst.value);
      }
      else {
        if (p.fst.left != null || p.fst.right != null) {
          p.snd = true;
          s.push(p);
          if (p.fst.right != null) 
            s.push(new Pair<TreeNode<T>, Boolean>(p.fst.right, false));
          if (p.fst.left != null) 
            s.push(new Pair<TreeNode<T>, Boolean>(p.fst.left, false));
        }
        else {
          l.add(p.fst.value);
        }
      }
    }
    return l;
  }

Has anyone guts here to make this program without stack and recursive method?