Binary tree post order traverse without recursion in Java

Post order traversal 

In PostOrder traversal, the left node is processed first, the right node (subtree), then the node.

Steps for post order are:

   1. Process left subtree.

   2. Process right subtree.

   3. Process the node.

I will consider processing the node is just printing out its value on screen.

Consider the below binary tree

Processing the above tree in post order should result the following:

                        1, 4, 6, 2, 12, 45, 40, 10, 75, 60, 50

The recursive solution is very straight forward by following the above steps:

    public void postOrderTravesalRecursion(){
        postOrderTravesalRecursion(this.root);
    }
   
    private void postOrderTravesalRecursion(Node node){
      
           if(node==null){
               return;
           }
           postOrderTravesalRecursion(node.getLeft());
           postOrderTravesalRecursion(node.getRight());
           System.out.println(node);
    }

Doing the same without using the recursion is a pretty tricky, a stack-based solution is necessary when there is no parent pointer available in the tree. also we need a variable to indicate if the node has been processed before.

 Algorithm steps: 
   1. Create a stack.
   2. Loop while the stack is not empty
   3. Current node is equal to root node
   4. If current node is not null push the node in the stack and keep moving left.
   5. If left is null, pop the node from the stack.
   6. If node has right child and the right child is not processed yet, set the right child to the current  
       node and repeat step 4
   7. If node doesn't have right child or the right child has been processed before, print the node and
       mark the node as processed.

The implementation
    public void postOrderTravesalIterative(){
                  Stack<Node> callingStack = new Stack<Node>();
                  Node currentNode = this.root;
                  Node proccessedNode = null;
      
                 while(currentNode!=null || !callingStack.isEmpty()){
          
                       if(currentNode!=null){
                           
                           callingStack.push(currentNode);
                           currentNode = currentNode.getLeft();

                       }else{
                           Node node = callingStack.pop();
              
                           if(node.getRight()!=null && node.getRight()!=proccessedNode){
                                currentNode =node.getRight();
                                callingStack.push(node);
                           }else{
                                 System.out.println(node);
                                 proccessedNode = node;
                          }
                     }
          
                 }
      
       }
     
    That is it, hope it is useful.