Like many tree algorithms, the easiest way to implement post-order traversal is by using

Unlike in-order traversal which prints all nodes of binary search tree in sorted order, post-order doesn't provide sorting but its useful while deleting nodes from binary tree, see a good book on data structure and algorithms e.g. Introduction to Algorithms by Thomas H. Cormen to learn more about different usage of post-order traversal in Computer Science and programming.

###

The recursive algorithm is very easy to understand as it 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, left subtree is visited first, the right subtree is visited second and value of the node is printed third. If you want to learn more about the recursive post-order traversal algorithm e.g. it's real world examples and complexity assesment, I suggest you to take a look at Algorithms 4th Edition by Robert Sedgewick, one of the best data structure and algorithm book for Java developers as examples are given in Java programming language.

###

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 algorithm 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 second one is private. The actual traversing is done in second method but since root is internal to the class and client don't have access to root, I have created postOrder() method which calls the private method. This is a common trick to implement recursive algorithm.

This also gives you luxury to change your algorithm without affecting clients e.g. 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 iterative algorithm is in place.

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

###

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;

}

}

printing nodes of a binary tree on post order in Java

15 25 87 98 45 35 75 65 55

**recursion**. In fact, if you know how to write pre-order using recursion, you can use the same algorithm with 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.Unlike in-order traversal which prints all nodes of binary search tree in sorted order, post-order doesn't provide sorting but its useful while deleting nodes from binary tree, see a good book on data structure and algorithms e.g. Introduction to Algorithms by Thomas H. Cormen 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 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, left subtree is visited first, the right subtree is visited second and value of the node is printed third. If you want to learn more about the recursive post-order traversal algorithm e.g. it's real world examples and complexity assesment, I suggest you to take a look at Algorithms 4th Edition by Robert Sedgewick, one of the best data structure and algorithm book for Java developers as examples are given in Java programming language.

###
**Java Program to print binary tree in 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 algorithm 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 second one is private. The actual traversing is done in second method but since root is internal to the class and client don't have access to root, I have created postOrder() method which calls the private method. This is a common trick to implement recursive algorithm.

This also gives you luxury to change your algorithm without affecting clients e.g. 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 iterative algorithm is in place.

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

###
**Printing nodes of 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