In the last couple of articles, you have learned about pre-order and in-order tree traversal algorithms in Java and today, you will learn about the post order traversal in a binary tree. It is the toughest of all three tree traversal algorithms and programmers generally struggle to implement this when asked in a coding interview, hence it makes sense to understand and practice this algorithm before going for the interview. The

In fact, if you know how to write pre-order using recursion, you can use the same algorithm with a bit of adjustment to implement post-order traversal. All you need to do is instead of printing the value of node first, just call the recursive method with left subtree as shown in our example.

Though non-recursive or an iterative version of post-order traversal is a bit difficult and that's why mostly asked during coding interviews, but if you remember a simple trick that a stack data structure can convert a recursive algorithm to iterative one then you can easily code post-order algorithms as well.

Anyway, that's not the topic of this article though, here we'll focus on recursive algorithms and I'll explain iterative algorithm on another article like I have done previously with iterative pre-order and in-order algorithms.

Unlike in-order traversal which prints all nodes of binary search tree in sorted order, post-order doesn't provide sorting but it is frequently used while deleting nodes from binary tree, see a good book or online course on data structure and algorithms like

##

The recursive algorithm is very easy to understand as it is exactly similar to the recursive preOrder and recursive inOrder traversal. The only thing which is different is the order in which the left subtree, right subtree, and root are visited or traversed as shown in following code snippet.

You can see that algorithm is exactly similar to pre-order algorithm except for the

If you want to learn more about the recursive post-order traversal algorithm like it's real-world examples and complexity assessment, I suggest you take a look at

##

Here is the complete Java program to print all nodes of a binary tree in the post-order traversal. In this part of the tutorial, we are learning the recursive post-order traversal and next part, I'll show you how to implement post order algorithm without recursion, one of the toughest tree traversal algorithms for beginner programmers.

Similar to our earlier examples, I have created a class called BinaryTree to represent a binary tree in Java. This class has a static nested class to represent a tree node, called TreeNode. This is similar to the Map. Entry class which is used to represent an entry in the hash table. The class just keep the reference to root and TreeNode takes care of left and right children.

This class has two methods postOrder() and postOrder(TreeNode root), the first one is public and the second one is private. The actual traversing is done in the second method but since root is internal to the class and client don't have access to root, I have created a postOrder() method which calls the private method. This is a common trick to implement a recursive algorithm.

This also gives you the luxury to change your algorithm without affecting clients like tomorrow we can change the recursive algorithm to an iterative one and client will still be calling the post order method without knowing that now the iterative algorithm is in place

And if you want to learn more about theory part of the binary tree and other fundamental data structure then please see

Anyway, here is the binary tree which you need to traverse in the post order, the problem is solved by the following example as well:

##

That's all about

This is also the reason why root is printed at last on post-order traversal. If you want to learn more about post order traversal or other binary tree algorithms, I suggest exploring the following resources to learn Data Structures and Algorithms in depth.

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Introduction to Algorithms by Thomas H. Cormen

Data Structure and Algorithms Specialization on Coursera

Other

**post order traversal**is also a depth-first algorithm because you go deep before you visit other nodes on the same level. In post order traversal, you first visit the left subtree, then right subtree and finally you print the value of node or root. That's why the**value of root is always printed last on post-order traversal**. Like many tree algorithms, the easiest way to implement post-order traversal is by using recursion.In fact, if you know how to write pre-order using recursion, you can use the same algorithm with a bit of adjustment to implement post-order traversal. All you need to do is instead of printing the value of node first, just call the recursive method with left subtree as shown in our example.

Though non-recursive or an iterative version of post-order traversal is a bit difficult and that's why mostly asked during coding interviews, but if you remember a simple trick that a stack data structure can convert a recursive algorithm to iterative one then you can easily code post-order algorithms as well.

Anyway, that's not the topic of this article though, here we'll focus on recursive algorithms and I'll explain iterative algorithm on another article like I have done previously with iterative pre-order and in-order algorithms.

Unlike in-order traversal which prints all nodes of binary search tree in sorted order, post-order doesn't provide sorting but it is frequently used while deleting nodes from binary tree, see a good book or online course on data structure and algorithms like

**Data Structures and Algorithms: Deep Dive Using Java**to learn more about different usage of post-order traversal in Computer Science and programming.##
__Post-order traversal using Recursion__

The recursive algorithm is very easy to understand as it is exactly similar to the recursive preOrder and recursive inOrder traversal. The only thing which is different is the order in which the left subtree, right subtree, and root are visited or traversed as shown in following code snippet.private void postOrder(TreeNode node) { if (node == null) { return; } postOrder(node.left); postOrder(node.right); System.out.printf("%s ", node.data); }

You can see that algorithm is exactly similar to pre-order algorithm except for the

**order of traversal to root, left sub-tree, and right subtree is different**. In this code, the left subtree is visited first, the right subtree is visited second and the value of the node is printed third.If you want to learn more about the recursive post-order traversal algorithm like it's real-world examples and complexity assessment, I suggest you take a look at

**Data Structure and Algorithms Specialization on Coursera**, one of the best data structure and algorithm resource for Java developers as examples are given in Java programming language.##
__Java Program to print the binary tree in a post-order traversal__

Here is the complete Java program to print all nodes of a binary tree in the post-order traversal. In this part of the tutorial, we are learning the recursive post-order traversal and next part, I'll show you how to implement post order algorithm without recursion, one of the toughest tree traversal algorithms for beginner programmers.Similar to our earlier examples, I have created a class called BinaryTree to represent a binary tree in Java. This class has a static nested class to represent a tree node, called TreeNode. This is similar to the Map. Entry class which is used to represent an entry in the hash table. The class just keep the reference to root and TreeNode takes care of left and right children.

This class has two methods postOrder() and postOrder(TreeNode root), the first one is public and the second one is private. The actual traversing is done in the second method but since root is internal to the class and client don't have access to root, I have created a postOrder() method which calls the private method. This is a common trick to implement a recursive algorithm.

This also gives you the luxury to change your algorithm without affecting clients like tomorrow we can change the recursive algorithm to an iterative one and client will still be calling the post order method without knowing that now the iterative algorithm is in place

And if you want to learn more about theory part of the binary tree and other fundamental data structure then please see

**Algorithms and Data Structures - Part 1 and 2**courses on Pluralsight. One of the best course for beginners.Anyway, here is the binary tree which you need to traverse in the post order, the problem is solved by the following example as well:

##
__Printing nodes of a binary tree in post order__

__Printing nodes of a binary tree in post order__

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 using post-order traversal using recursion System.out.println("printing nodes of a binary tree on post order in Java"); bt.postOrder(); } } 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); } /** * 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; } } Output printing nodes of a binary tree on post order in Java 15 25 87 98 45 35 75 65 55

That's all about

**how to implement post order traversal in Java**. You can use this algorithm to print all nodes of a binary tree in post order. Just remember that in post-order traversal, you first visit left subtree, followed by right subtree and finally the value of node or root is printed.This is also the reason why root is printed at last on post-order traversal. If you want to learn more about post order traversal or other binary tree algorithms, I suggest exploring the following resources to learn Data Structures and Algorithms in depth.

**Further Learning**Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Introduction to Algorithms by Thomas H. Cormen

Data Structure and Algorithms Specialization on Coursera

Other

**Binary tree tutorials in Java,**you may like to explore- Top 5 data structure and algorithm books for coding interviews (list)
- How to implement pre-order traversal in Java? (solution)
- Java Program to traverse a binary tree in pre-order without recursion (program)
- How to implement in-order traversal in Java? (solution)
- How to implement in-order traversal in Java without recursion? (solution)
- 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 a linked list using generics in Java? (solution)
- How to reverse a singly linked list in Java? (solution)
- How to find the 3rd element from the end of a linked list 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)
- How to reverse an array in place in Java? (solution)
- How to print duplicate elements of an array in Java? (solution)

**P. S.**- If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the

**Easy to Advanced Data Structures**course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.

Your tree structure is not drawn correctly in image as well as javadoc, with respect to coding.

ReplyDeleteYeah, thank for pointing it out, I'll correct it.

Delete