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

Now, let's see the utility of

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

Good knowledge of these 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

##

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:

If you look at this method you will find that

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

It's offered by the University of California and you can access it for free if you don't need a certificate, but if you need, maybe to add into your resume and LinkedIn profile, by all means, subscribe this specialization.

And, if you like a book, just read

##

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, traditional tool to convert a recursive algorithm to an iterative one.

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

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

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structure and Algorithms Specialization on Coursera

Cracking the Coding Interview - 189 Questions and Solutions

**depth-first algorithm**, you have to go deep before you go wide. I mean, 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 you use the 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 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 leaves***use 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.Good knowledge of these 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 on Udemy 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 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.Iterative Algorithm to implement post order traversal of Binary Tree

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 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 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. 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.It's offered by the University of California and you can access it for free if you don't need a certificate, but if you need, maybe to add into your resume and LinkedIn profile, by all means, subscribe this specialization.

And, if you like a book, just read

**Introduction to Algorithms**book by Thomas H. Cormen to learn more about essential data structures and algorithms.##
__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, 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 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.**Further Learning**Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structure and Algorithms Specialization on Coursera

Cracking the Coding Interview - 189 Questions and Solutions

Other

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.

**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 a 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)
- 10 Algorithms Courses to Crack Coding Interviews (courses)
- How to print all leaf nodes of a binary tree without recursion in Java? (solution)
- How to implement a linked list using generic in Java? (solution)
- How to reverse a singly linked list in Java? (solution)
- How to traverse a binary tree in pre-order without using recursion? (solution)
- 50+ Data Structure Problems from Coding Interview (questions)
- 10 (Free) Data Structure and Algorithms Courses for Devs (courses)
- How to find the 3rd element from the end of a linked list in Java? (solution)
- How to reverse an array in place in Java? (solution)
- How to find the middle element of linked list using a single pass? (solution)
- Java program to implement binary search using recursion? (solution)
- 10 Data Structure Books Every Programmer Should Read (books)
- How to print duplicate elements of an array in Java? (solution)
- Top 10 Courses to Learn Data Structure and Algorithms in Java (courses)
- 20 String Problems from Coding Interviews (question)

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.

**P.S.**- If you don't mind learning from free resources then you can also take a look at my list of**free data structure and algorithm courses**for Java developers.
That's a bit presumptuous destroying the original data... Instead of doing that, you could keep track of hosts already output in a HashSet.

ReplyDeleteI think it's better to use solution without changing data in nodes.

ReplyDeletepublic static void postOrderTraversalWithoutRecursion(BinaryTree binaryTree) {

Node top = binaryTree.top;

if(top == null) {

System.out.println("Empty Binary Tree");

return;

}

Stack stack = new Stack<>();

stack.push(top);

Node lastPrintedNode = top;

Node current;

while (!stack.isEmpty()) {

current = stack.pop();

if(current.isLeaf() || lastPrintedNode == current.right || lastPrintedNode == current.left) {

System.out.printf("%s, ", current.value);

lastPrintedNode = current;

} else {

stack.push(current);

if(current.right != null) {

stack.push(current.right);

}

if(current.left != null) {

stack.push(current.left);

}

}

}

}

There is an issue with the diagram that is used. It is not consistent with the code.

ReplyDelete