CareerCup

In the following element we have a new field called parsed in the node data structure.. and it is set to false initially.

We can use a stack...

1. first push the element and set the value of parsed for this element to true, then the right child, and then the left child. If not children, nothing to be be pushed on the stack.
2. Now pop the last element on the stack, see if it is parsed.. If not then follow step 1. If yes, go to step 3.
3. Print the element. and pop it out.

import java.util.Scanner;
import java.util.Stack;

public class PostOrder {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Node root = readTree(in);
		Stack<Action> stack = new Stack<Action>();
		stack.push(new VisitNode(stack, root));
		while (!stack.empty()) {
			stack.pop().act();
		}
	}

	static Node readTree(Scanner in) {
		int value = in.nextInt();
		if (value == 0) {
			return null;
		} else {
			Node node = new Node();
			node.value = value;
			node.left = readTree(in);
			node.right = readTree(in);
			return node;
		}
	}
}

class Node {
	int value;
	Node left, right;
}

interface Action {
	void act();
}

class VisitNode implements Action {
	Stack<Action> stack;
	Node node;

	VisitNode(Stack<Action> s, Node n) {
		stack = s;
		node = n;
	}

	public void act() {
		if (node != null) {
			stack.push(new PrintValue(node.value));
			stack.push(new VisitNode(stack, node.right));
			stack.push(new VisitNode(stack, node.left));
		}
	}
}

class PrintValue implements Action {
	int value;

	PrintValue(int v) {
		value = v;
	}

	public void act() {
		System.out.println(value);
	}
}

void postOrder(Node root) {
Stack stack1, stack2;

stack1.push(root);
while(!stack1.isEmpty()){
Node tmp = stack1.pop();
stack2.push(tmp);
if(tmp.left != null) {
stack1.push(tmp.left);
}
if(tmp.right != null) {
stack1.push(tmp.right);
}
}

while(!stack2.isEmpty()) {
System.out.println(stack2.pop().data);
}
}

en.wikipedia.org/wiki/Tree_traversal

Okay kids...

void postorder() {
  stack<BSTNode**> s;
  BSTNode** n = &_root;
  BSTNode** prev = &_root;
  while (true) {
    if (n != NULL && *n != NULL) {
      s.push(n);
      n = &((*n)->left);
    } else {
      if (!s.empty()) {
        n = s.top();
        if (*prev == (*n)->right) {
          printf("%d\n", (*n)->data);
          s.pop();
          prev = n;
          n = NULL;
        } else {
          prev = n = &((*n)->right);
        }
      } else {
        break;
      }
    }
  }
}

One similar solution using single stack :

void postorder (tree_node * root) {
stack<tree_node *> s;
tree_node *p_n = root, *temp = NULL, *prv = NULL;

if(root == NULL)
return;

while(true){
while(p_n != NULL){
s.push(p_n);
p_n = p_n->left;
}
temp = s.top();
if(prv == temp){
cout << prv->data << ",";
s.pop();
if(s.empty())
break;
} else {
if(temp->right != prv){
p_n = temp->right;
prv = temp;
}else {
cout << temp->data << ",";
s.pop();
prv = s.top();
if(prv->right == temp){
p_n = NULL;
}
else
p_n = prv->right;
}
}
}
}

push(root) // push root into stack
while(true) // stack not empty
{
node = pop()
if(node->right == null && node->left == null)
print node->data
else
{
push(node);
if(node->right != null)
push(node->right)
if(node->left != null)
push(node->left)
}
}

void postOrder(Node root) {
Stack stack1, stack2;

stack1.push(root);
while(!stack1.isEmpty()){
Node tmp = stack1.pop();
stack2.push(tmp);
if(tmp.left != null) {
stack1.push(tmp.left);
}
if(tmp.right != null) {
stack1.push(tmp.right);
}
}

while(!stack2.isEmpty()) {
System.out.println(stack2.pop().data);
}
}


The solution given by anonymous doesnt even works. And people are praising him without solving it with a example.

@alahomora...great job..

@alahomora very good!!

public void postOrderTraversalWithoutRecursion(Node node){
		if(node == null){
			return;
		}		
		Stack<Node> stack = new Stack<Node>();
		Node prev = null;
		
		if(node != null)
		stack.push(node);
		
		while (!stack.isEmpty()){
			Node curr = stack.peek();
			if(prev == null || prev.getLeft() == curr || prev.getRight() == curr){
				
				if(curr.getLeft() != null){
					stack.push(curr.getLeft());
				}	else if (curr.getRight() != null)	{
					stack.push(curr.getRight());
				}
			}	else if( curr.getLeft() == prev){
				if(curr.getRight() != null){
					stack.push(curr.getRight());
				}
			}	else	{
				System.out.print(curr.getValue());
				stack.pop();
			}
			prev = curr;
		}
	}