Post Order binary tree traversal in Java - Recursion and Iteration

This is the third article on tree traversal. In the last couple of articles, I have shown you how to implement preorder and inorder traversal in Java, both recursively and iteratively and today, you will learn about the post order traversal. Out of these three main tree traversal algorithms, the post-order traversal is most difficult to implement, especially the iterative version. In post order traversal, you first visit left subtree, then right subtree and at last you print the value of root or not. So, the value of root is always printed at last in the post-order traversal. As I told you before, all three preOrder, inOrder, and postOrder are depth-first algorithms so they go down in the binary tree first before visiting nodes of the same level. The implementation of the recursive algorithm is very simple, you just need to adjust the order of recursive call according to the algorithm and you are done, but iterative algorithm requires some effort to get it right, which you will see in this article.


Unlike inorder traversal which prints the nodes of binary search tree in sorted order, post order doesn't print values in sorted order but it can be used to generate a postfix representation of a binary tree. It's also particularly important while deleting nodes of binary tree e.g. if you don't use post-order traversal during deletion, then you lose the references you need for deleting the child trees. These were just couple of usage of post order tree traversal, you can see a good algorithm book like Introduction to Algoirthms by Thomas H. Cormen or Algorithms 4th Edition by Robert Sedgewick to learn more about them.


Problem statement:  Print nodes of following binary tree in post order
        45
       / \
      25  55
     / \    \
    15  35   65
   /   /  \
  5   77   88

Output: 5 15 35 25 77 88 65 55 45 

Post Order traversal of binary tree in Java using Recursion

Let's first see the recursive solution which is extremely easy to code, especially if you know how to impelment pre order  and in order using recursion. All you need to do is change the order of recursive call according to algorihtm as per following steps of post order algorithm.

1) visit the left subtree
2) visit the right subtree
3) print the value of current node or root.


So in case of given binary tree, we start with root(45) and then go to left, node(25), then again we go to left until we reach the leaf node 5. At this time, we try to go right subtree now, but there is nothing there so we print the value of node. Now, we start to go up to node 15, there is no right subtree here so we again print the value of 15.

Now, we come back to 25, here we have right subtree so we go there and reach another leaf node 35, we print its value and comeback to 25, since both 15 and 35 are visited we print its value and go back to 45. Now we start to right subtree because left subtree of node 45 is fully explored and reach to node 55. Since there is no left subtree, we go again to 65, which has left subtree, so we go to 77 and prints its value as its a leaf node, we come back to 65 and go to right subtree and print 88 because its leaf node, now we come back again to 65 and prints value.

Similarly we go up to 55 and since left and right subtree is full explored we prints its value and come back to root. Now since both left and right subtree of root is fully visited, we print the value of root and algorithm finished since all nodes are visited.

Here is a post order implementation in Java using recursion:

private void postOrder(TreeNode node) {
    if (node == null) {
      return;
    }

    postOrder(node.left);
    postOrder(node.right);
    System.out.printf("%s ", node.data);
  }

The code is exactly similar to recurive preOrder and InOrder algorithm with only change that postOrder() funciton call is now made for left and right subtree before printing value of node. The node == null is still serve ras base case of this solution. Btw, if you struggle with recursion or understand recursion but don't know how to come up with a recursive algorithm for a problem, I would suggest reading Grokking Algorithm, one of the newest book on the algorithm and I guess most readable of all of them.

Post Order binary tree traversal in Java - Iterative and Recursive



Binary Tree Post Order Traversal in Java without Recursion

The iterative post order traversal algoirthms is the most difficult betwen all three iterative tree traversal algorithm e.g. pre order, in order and post order. Like other itrative algorithm, we use a Stack to store nodes. We start with root by pusing it into Stack and loop until Stack is empty. In every iteration we peek() the current node from Stack, remember unlike preOrder, we use peek() and not pop() method. The peek() method return the top of the Stack without removing it. If current node is lead node then we print its value. Otherwise we check current node has right and left subtree and then we push those nodes into Stack and mark them null to signify they are already in Stack or visited.

Since, we need to visit left subtree first, we push the right node first beause Stack is LIFO data structure and last inserted node will reamin at the top of the stack. we repeat the same process until we visit all the nodes, at this point tree is traversed using post order algorithm. If you want to learn more about Stack and how to convert a recursive algorithm to iterative one, please refer a good algorithm book like Introduction to Algorithms by Thomas H. Cormen.

Here is the Java implementation of iterative post-order traversal algorithm of a binary tree:

public void postOrderWithoutRecursion() {
    Stack 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;
        }
      }

    }
  }

You can see that we first check for leaf node and if it's leaf we print its value. Remember to mark current.left and current.right node null otherwise your program will never finish and code will go into infinite loop.

Post Order binary tree traversal in Java with and without recursion


Java Program to traverse binary tree in post order algorithm

Here is our complete program to print all nodes of binary tree as per post order traversal in Java. You can also use this algoirthm to collecte all nodes in a list, for now we are just printing. This program implements post order traversal both with and without recursion. We also use the same BinaryTree and TreeNode class which we have used to implement binary search tree, only differnece is that this time we have not made TreeNode implements Comparable interface. The recursive logic is coded in postOrder(TreeNode root) method and iterative algorithm is coded into postOrderWithoutRecursion() method.

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:
*       45
*      / \
*     25  55
*    / \    \
*   15  35   65
*  /   /  \
* 5   77   88
* 
* output: 5 15 35 25 77 88 65 55 45 
*/

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 using post order traversal using recursion
System.out.println("printing nodes of binary tree on post order using recursion");

bt.postOrder();

System.out.println(); // insert new line

// 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;

/**
* traverse the binary tree on post order traversal algorithm
*/
public void postOrder() {
postOrder(root);
}

private void postOrder(TreeNode node) {
if (node == null) {
return;
}

postOrder(node.left); 
postOrder(node.right);
System.out.printf("%s ", node.data);
}

public void postOrderWithoutRecursion() {
Stack 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("45");
tree.root = root;
tree.root.left = new TreeNode("25");
tree.root.left.left = new TreeNode("15");
tree.root.left.left.left = new TreeNode("5");

tree.root.left.right = new TreeNode("35");
tree.root.right = new TreeNode("55");
tree.root.right.right = new TreeNode("65");
tree.root.right.right.left = new TreeNode("77");
tree.root.right.right.right = new TreeNode("88");



return tree;
}

}

Output
printing nodes of a binary tree on post order using recursion
5 15 35 25 77 88 65 55 45 
printing nodes of a binary tree on post order using iteration
5 15 35 25 77 88 65 55 45 



That's all about how to traverse a binary tree in post order. The recursive post order traversal is pretty easy but the iterative post order algorithm is quite tough. This also shows point that sometime a recursive solution is much more easier and readable than iterative one e.g. post order tree travesal or tower of hanoi. The algorithm is simple but its difficult to implement using Stack and candidate often make mistake while coming up to tree from leaf node.

Nevertheless this complete the three part series of articles about binary tree traversal. I am thinking to extend this series to cover other tree traversal algorithms e.g. level order traversal or spiral leel order traversal. In the meantime, if you want to enjoy learning algorithms, you can refer Grokking Algorithms: An illustrated guide for programmers and other curious people 1st Edition by Aditya Bhargava, one of the interesting books on Algorithms with lots of real world examples and a different style of explanation.


 Other binary tree and data structure tutorials you may like to explore
  • 5 data structure and algorithm books for coding interviews (list)
  • How to implement pre-order traversal in Java?  (solution)
  • How to implement in-order traversal in Java? (solution)
  • How to print all leaf nodes of a binary tree in Java? (solution)
  • How to implement in-order traversal in Java without recursion? (solution)
  • 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 find the middle element of linked list using single pass? (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 reverse an array in place in Java? (solution)
  • How to print duplicate elements of an array in Java? (solution)

References



5 comments :

Hendi Santika's Blog said...

Nice share. Nice Article.

I have tried this example too.
But the result was still the same.
It it said "incompatible types: Object cannot be converted to TreeNode">

Could you please give me an advise?

Thanks a lot.

Javin Paul said...

Hello Hendi, can you post the stacktrace please?

Anonymous said...

Are you sure that order of elements for postorder should be: 5 15 35 25 77 88 65 55 45 ?
Shouldn't it be 5 15 77 88 35 25 65 55 45?

Kavita Laddha said...

I agree wit the comment above, shouldn't the output above be 5 15 77 88 35 25 65 55 45?

Javin Paul said...

@Anonymous and @Kavita, good catch, but can you spot the error in code? would be fun :-) I'll post the correction but I want you guys to suggest me where is the bug in this code?

Post a Comment