Post Order Binary Tree Traversal in Java Without Recursion

In the last article, I have shown you how to implement post-order traversal in a binary tree using recursion, and today I am going to teach you about post order traversal without recursion. To be honest, the iterative algorithm of post-order traversal is the toughest among the iterative pre-order and in-order traversal algorithm. The process of post-order traversal remains the same but the algorithm to achieve that effect is different. Since post-order traversal is a depth-first algorithm, you have to go deep before you go wide. I mean, the left subtree is visited first, followed by the right subtree, and finally, the value of a node is printed.

This is the reason why the value of root is printed last in the post-order traversal algorithm.

Now, let’s see the utility of the post-order traversal algorithm, what do you get from it and when do you use the post-order algorithm to traverse a binary tree? As oppose to inorder traversal which prints nodes of the binary search tree in sorted order and can also be used to flatten a binary tree in the same order it was created, post-order traversal can be used to inspect leaves before you inspect root. It can also be used to generate a postfix sequence.

Now, one of the frequently asked questions is when do you use pre-order, post-order, or in-order traversal while dealing with binary tree data structure?

The general point regarding usage of traversal algorithm is based on the requirement of your application like if you want to inspect all roots before leavesuse pre-order and if you want to inspect leaves before root then use the post-order traversal algorithms, and if you want to visit all nodes in the sorted order then you can use in-order traversal algorithm.

As a programmer, you should know about fundamental binary tree algorithms is essential to pass any coding interview and if haven’t spend a good deal of your time in your school and collages understanding these data structure fundamentals, I suggest you join the Data Structures and Algorithms: Deep Dive Using Java course to learn more about not just when to use pre-order, in-order, and post-order traversals, but also refresh all other fundamental data structure and algorithms.

Iterative Algorithm to implement post-order traversal of Binary Tree

The recursive algorithm of post-order traversal which we have seen in the previous article was quite similar to recursive pre-order and recursive in order algorithms, all you need to do was adjust the order of recursive function call to match the order on which left subtree, right subtree, and root needs to traverse, but the iterative algorithm of post-order traversal is very different than iterative pre-order and in-order traversal.

In fact, it’s the most difficult to implement among the three traversal algorithms. Sure, you still use an explicitly Stack data structure to store elements, but the backtracking and then exploring the right subtree is a little bit tricky to implement.

Here is one of the simplest post-order traversal algorithms without using recursion:

public void postOrderWithoutRecursion() {
    Stack<TreeNode> nodes = new Stack<>();
    nodes.push(root);

    while (!nodes.isEmpty()) {
      TreeNode current = nodes.peek();

      if (current.isLeaf()) {
        TreeNode node = nodes.pop();
        System.out.printf("%s ", node.data);
      } else {

        if (current.right != null) {
          nodes.push(current.right);
          current.right = null;
        }

        if (current.left != null) {
          nodes.push(current.left);
          current.left = null;
        }
      }

    }
  }

If you look at this method you will find that we are examining leaves before examining roots. We start the post-order traversal from the root by pushing it into a Stack and then loop until our Stack is empty.

At each iteration, we peek() the element from Stack, I mean, we retrieve it without removing and check if it’s a leaf, if yes then we pop() the element and print its value, which means the node is visited.

If it’s not a leaf then we check whether it has a right node, if yes we store into a tree and set it to null, similarly, we check if it has left a node, if yes we push into the stack, and then mark it null.

We first insert the right node because Stack is a LIFO (last in first out) data structure and as per post-order traversal we need to explore the left subtree before the right subtree. If you are not familiar with Stack (LIFO) and Queue (FIFO) data structure which is used in level order traversal, I suggest you take a look at the Data Structure and Algorithms Specialization on Coursera one of the best resources to master this topic.

Java Program for Binary tree PostOrder traversal

Here is our complete Java program to implement post order traversal of a binary tree in Java without using recursion. The iterative algorithm is encapsulated inside the postOrder() method. We have used the same BinaryTree and TreeNode class to implement a binary tree and then added the postOrder() method to print all nodes of a binary tree into post order.

The algorithm we have used doesn’t need recursion and it instead uses a while loop and a Stack, a traditional tool to convert a recursive algorithm to an iterative one.

import java.util.Stack;

/*
 * Java Program to traverse a binary tree 
 * using postOrder traversal without recursion. 
 * In postOrder traversal first left subtree is visited, 
   followed by right subtree
 * and finally data of root or current node is printed.
 * 
 * input:
 * 55
 * / \
 * 35 65
 * / \ \
 * 25 45 75
 * / / \
 * 15 87 98
 * 
 * output: 15 25 45 35 87 98 75 65 55 
 */

public class Main {

  public static void main(String[] args) throws Exception {

    // construct the binary tree given in question
    BinaryTree bt = BinaryTree.create();

    // traversing binary tree on post order traversal without recursion
    System.out
        .println("printing nodes of binary tree on post order using iteration");
    bt.postOrderWithoutRecursion();
  }

}

class BinaryTree {
  static class TreeNode {
    String data;
    TreeNode left, right;

    TreeNode(String value) {
      this.data = value;
      left = right = null;
    }

    boolean isLeaf() {
      return left == null ? right == null : false;
    }

  }

  // root of binary tree
  TreeNode root;

  /**
   * Java method to print all nodes of tree in post-order traversal
   */
  public void postOrderWithoutRecursion() {
    Stack<TreeNode> nodes = new Stack<>();
    nodes.push(root);

    while (!nodes.isEmpty()) {
      TreeNode current = nodes.peek();

      if (current.isLeaf()) {
        TreeNode node = nodes.pop();
        System.out.printf("%s ", node.data);
      } else {

        if (current.right != null) {
          nodes.push(current.right);
          current.right = null;
        }

        if (current.left != null) {
          nodes.push(current.left);
          current.left = null;
        }
      }

    }
  }

  /**
   * Java method to create binary tree with test data
   * 
   * @return a sample binary tree for testing
   */
  public static BinaryTree create() {
    BinaryTree tree = new BinaryTree();
    TreeNode root = new TreeNode("55");
    tree.root = root;
    tree.root.left = new TreeNode("35");
    tree.root.left.left = new TreeNode("25");
    tree.root.left.left.left = new TreeNode("15");

    tree.root.left.right = new TreeNode("45");
    tree.root.right = new TreeNode("65");
    tree.root.right.right = new TreeNode("75");
    tree.root.right.right.left = new TreeNode("87");
    tree.root.right.right.right = new TreeNode("98");

    return tree;
  }

}

When you will run this program in your favorite IDE e.g. Eclipse or IntelliJIDea, you will see the following output:

Output
printing nodes of a binary tree on post order using iteration
15 25 45 35 87 98 75 65 55 

You can see that nodes are printed in the post order. You can also see the value of the root node is printed last.

That’s all about how to implement post order traversal of a binary tree in Java. Just remember, it is also a depth-first algorithm, but you need to visit the left subtree first, followed by the right subtree and root. The iterative version is also very difficult to implement you go exactly by the steps of post-order traversal. The version which I have shared is much easier to understand and implement.