Binary Tree Post Order Traversal in Java Without Recursion - Example Tutorial

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 same but the algorithm to achieve that effect is different. Since post-order traversal is a depth-first algorithm, you go deep before you go wide. The left subtree is visited first, followed by 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 post-order traversal algorithm, what do you get from it and when do yo use post-order algorithm to traverse a binary tree? As oppose to inorder traversal which prints node 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 postfix sequence.

Now, one of the frequently ask question 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 e.g. if you want to inspect all roots before leaves use pre-order and if you want to inspect leaves before root then use post-order traversal.   If you want to visit all nodes in the sorted order then you can use in-order traversal algorithm. You can also read Introduction to Algorithms to learn more about when to use pre-order, in-order, and post-order traversals.




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 you to do was adjust the order of recursive function call to match the order on which left subtree, right subtree, and root needs to traversed, but 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 three traversal algorithm. Sure, you still use an explicitly Stack data structure to store elements, but the backtracking and then exploring right subtree is a little bit tricky to implement.

Here is one of the simplest post-order traversal algorithm 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 root. We start the post order traversal from the root by pushing it into a Stack and then loop until out Stack is empty. At each iteration, we peek() the element from Stack i.e. 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 if 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 right node because Stack is a LIFO (last in first out) data structure and as per post order traversal we need to explore left subtree before right subtree




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 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, 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 root node is printed last.

Binary Tree Post Order Traversal in Java Without Recursion


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 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.


Other Data Structure and Algorithm tutorials  in Java, you may like to explore
  • Top 5 data structure and algorithm books for coding interviews (list
  • Java Program to traverse binary tree in pre-order without recursion (program)
  • How to print all leaf nodes of a binary tree in Java? (solution
  • Java Program to print leaf nodes of a binary tree without recursion? (program)
  • How to traverse a binary tree in pre-order without using recursion? (solution
  • How to print all leaf nodes of a binary tree without recursion in Java? (solution
  • How to implement linked list using generic in Java? (solution
  • How to reverse a singly linked list in Java? (solution
  • How to find the 3rd element from the end of linked list in Java? (solution)
  • How to find the middle element of linked list using single pass? (solution
  • Java program to implement binary search using recursion? (solution
  • How to reverse an array in place in Java? (solution
  • How to print duplicate elements of an array in Java? (solution)

Thanks for reading this article so far. If you like this tutorial and interview question then please share with your friends and colleagues. If you have any feedback or question then please drop a comment and I'll try to answer your query. If you want to learn more about essential data structures and algorithms then just read Introduction to Algorithms.

No comments:

Post a Comment