Post order traversal of binary tree without recursion

Question

What is the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion?

Answer 1

Here's the version with one stack and without a visited flag:

private void postorder(Node head) {   if (head == null) {     return;   }   LinkedList<Node> stack = new LinkedList<Node>();   stack.push(head);    while (!stack.isEmpty()) {     Node next = stack.peek();      boolean finishedSubtrees = (next.right == head || next.left == head);     boolean isLeaf = (next.left == null && next.right == null);     if (finishedSubtrees || isLeaf) {       stack.pop();       System.out.println(next.value);       head = next;     }     else {       if (next.right != null) {         stack.push(next.right);       }       if (next.left != null) {         stack.push(next.left);       }     }   } }