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

Iterative postorder traversal is not easy as non-recursive preorder and non-recursive inorder. Why? -In preorder and inorder traversal after visiting node it is removed from stack and we do not need 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. Post order traversal using one stack needs special treatment with tree, however using 2 stack postorder traversal can be done very easily. Consider following binary tree and it's preorder & postorder traversal sequence.

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

In order to achieve post order traversal using two stack problem can be split into two parts:-
1. Create reverse post order traversal in a stack - using modified preorder traversal and extra stack.
2. Iterate stack with reverse postorder traversal and display postorder sequence- LIFO property of stack.
As we have discussed about iterative preorder traversal.
What is modified preorder traversal - Instead of displaying/processing current node, push that node into stack. And push left sub-tree node before right sub-tree node into stack.

Algorithm:-
1. Push root to first stack
2. Loop until, stack-1 is not empty.
    2.1 pop node from stack-1 and push in stack-2
    2.2 Do check for existence of left and right child of current node,if exist, push them to stack-1.
3. Repeat step 2 and on loop exit, pop nodes from stack-2 and display in postorder.

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

Sample code - iterative postorder traversal using two stack 

/* reverseStack is reverse post order traversal stack */
 private void tweakedPreorderTraversal(Node root, Stack<Node> reverseStack) {
  /* java.util.Stack */
  Stack<Node> stack = new Stack<>();
  if (root != null) {
   /* push root into stack if root is not null */
   stack.push(root);
   /* Loop until stack is not empty */
   while (!stack.isEmpty()) {
    root = stack.pop();
    /* Push into stack-2, instead of displaying/processing */
    reverseStack.push(root);
    Node lc = root.getLeftChild();
    Node rc = root.getRightChild();
    /* If left child exist, push into stack */
    if (lc != null) {
     stack.push(lc);
    }

    /* If right child exist, push into stack */
    if (rc != null) {
     stack.push(rc);
    }

   }// End while loop
  }
 }

Complete sample program for iterative postorder traversal using two stack 

package com.devinline.trees;

import java.util.Stack;

public class IterativePostOrderUsingTwoStack {
 public String iterativePostorderTraversalUsingTwoStack(Node root) {
  StringBuffer sbf = new StringBuffer();
  /* java.util.Stack */
  Stack<Node> stack = new Stack<>();
  tweakedPreorderTraversal(root, stack);
  /* Iterate reverse post order traversal stack */
  while (!stack.isEmpty()) {
   sbf.append(stack.pop().getData() + " ");
  }
  return sbf.toString();
 }

 /* reverseStack is reverse post order traversal stack */
 private void tweakedPreorderTraversal(Node root, Stack<Node> reverseStack) {
  /* java.util.Stack */
  Stack<Node> stack = new Stack<>();
  if (root != null) {
   /* push root into stack if root is not null */
   stack.push(root);
   /* Loop until stack is not empty */
   while (!stack.isEmpty()) {
    root = stack.pop();
    /* Push into stack-2, instead of displaying/processing */
    reverseStack.push(root);
    Node lc = root.getLeftChild();
    Node rc = root.getRightChild();
    /* If left child exist, push into stack */
    if (lc != null) {
     stack.push(lc);
    }

    /* If right child exist, push into stack */
    if (rc != null) {
     stack.push(rc);
    }

   }// End while loop
  }
 }

 public static void main(String[] args) {
  IterativePostOrderUsingTwoStack ipo2SObj = new IterativePostOrderUsingTwoStack();
  Node root = ipo2SObj.new BinaryTree().createTree();
  String nodesStr = ipo2SObj
    .iterativePostorderTraversalUsingTwoStack(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
==================================