Iterative(non-recursive) postorder traversal of binary tree in Java - Using one stack

Iterative postorder traversal is not easy as iterative preorder and iterative inorder. Why? -In preorder and inorder traversal after visiting node it is removed from stack and we do not need  visit it again. However in postorder traversal, after processing both left and right subtree control returns back to current node and each node in post order traversal is traversed twice, once after visiting left subtree and another after visiting right subtree. So the trick here is to devise some way to differentiate between - whether we are returning from left subtree and right subtree.
"After popping of element from stack - check whether popped element and right child of stack top element are same or not" - if same we have covered both left and right subtree, pop one more element and display otherwise, process right child.

Node visit sequence in postorder -  56 78 11 43 23 98 12 18 12
Algorithm:-

1. If tress is not empty(root is not null), push all right child followed by current node into stack.
2. Loop until stack is not empty. Pop an element and check whether popped element has right child or not -
   If right child exist and poppedElement.rightChild == stackTop, then process right child before(pop stack and puch popped element back to stack)
   Otherwise, we have processed both left and right child - display popped element 
3.  Repeat 1 to 3, and exit outer loop when stack is empty. 
4. Process/display root of the tree.

Time and space complexity :- Time complexity is order of O(n) and space complexity is O(n).

Sample code for postorder traversal of binary tree in Java - Using one stack 

public String iterativePostorderTraversalUsingOneStack(Node root) {
 StringBuffer sbf = new StringBuffer();
 /* java.util.Stack */
 Stack<Node> stack = new Stack<>();
 if (root != null) {
  while (true) {
   /*
    * Traverse tree until left child exist and push right and
    * current node into stack
    */
   while (root != null) {
    if (root.rightChild != null)
     stack.push(root.rightChild);
    stack.push(root);
    root = root.leftChild;
   }

   /* Pop an element from stack */
   root = stack.pop();

   /* Exit outer loop, if stack is empty */
   if (stack.isEmpty()) {
    break;
   } else {
    /*
     * check whether root's right child exist or not .If exist
     * process it before root
     */
    if (root.rightChild != null
      && root.rightChild.equals(stack.peek())) {
     stack.pop();
     stack.push(root);
     root = root.rightChild;
    } else {
     sbf.append(root.getData() + " ");
     root = null;
    }
   }
  }
 }
 /* process root of the tree,once stack is empty and root is not null*/
 if (root != null) {
  sbf.append(root.data);
 }
 return sbf.toString();
}

Explanation:- As discussed in algorithm, traverse tree and push right child followed by current node (root) into stack. On each pop operation, check whether right child of that popped element exist or not(root.rightChild != null && root.rightChild.equals(stack.peek()), if exist pop the current eleemnt from stack which is right child of tree and push previously popped element(root) otherwise process node because both left and right has been processed.

Complete sample program of postorder traversal of binary tree in Java - Using one stack

package com.devinline.trees;

import java.util.Stack;

public class IterativePostOrderUsingOneStack {
public String iterativePostorderTraversalUsingOneStack(Node root) {
 StringBuffer sbf = new StringBuffer();
 /* java.util.Stack */
 Stack<Node> stack = new Stack<>();
 if (root != null) {
  while (true) {
   /*
    * Traverse tree until left child exist and push right and
    * current node into stack
    */
   while (root != null) {
    if (root.rightChild != null)
     stack.push(root.rightChild);
    stack.push(root);
    root = root.leftChild;
   }

   /* Pop an element from stack */
   root = stack.pop();

   /* Exit outer loop, if stack is empty */
   if (stack.isEmpty()) {
    break;
   } else {
    /*
     * check whether root's right child exist or not .If exist
     * process it before root
     */
    if (root.rightChild != null
      && root.rightChild.equals(stack.peek())) {
     stack.pop();
     stack.push(root);
     root = root.rightChild;
    } else {
     sbf.append(root.getData() + " ");
     root = null;
    }
   }
  }
 }
 /* process root of the tree,once stack is empty */
 if (root != null) {
  sbf.append(root.data);
 }
 return sbf.toString();
}

 public static void main(String[] args) {
  IterativePostOrderUsingOneStack ipo2SObj = new IterativePostOrderUsingOneStack();
  Node root = ipo2SObj.new BinaryTree().createTree();
  String nodesStr = ipo2SObj
    .iterativePostorderTraversalUsingOneStack(root);
  System.out.println("Postorder traversal is: " + nodesStr);
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   return root;
  }
 }

 class Node {

  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }
}

======Sample output==============
Postorder traversal is: 56 78 11 43 23 98 12 18 12

===============================

Read:- Iterative(non-recursive) post order traversal using two stack in Java