Binary Tree PostOrder traversal in java

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

This is 3rd part of java binary tree tutorial.

Table of Contents

PostOrder traversal
- Recursive solution
- Iterative solution:
Java Binary tree tutorial
- Was this post helpful?

In this post, we will see about PostOrder binary tree traversal in java.

PostOrder traversal

In PostOrder traversal, each node is processed after subtrees traversal.In simpler words,Visit left subtree, right subtree and then node.

Steps for PostOrder traversal are:

Traverse the left subtree in PostOrder.
Traverse the right subtree in PostOrder.
Visit the node.

There can be two ways of implementing it

Recursive
Iterative

Recursive solution

Recursive solution is very straight forward.Below diagram will make you understand recursion better.

Code for recursion will be:

// Recursive Solution

public void postOrder(TreeNode root) {

if(root != null) {

postOrder(root.left);

postOrder(root.right);

//Visit the node by Printing the node data

System.out.printf("%d ",root.data);

}

Iterative solution:

Steps for iterative solution:

Create an empty stack s and set currentNode =root.
while currentNode is not NULL Do following
1. Push currentNode 's right child and then currentNode to stack s
2. Set currentNode=currentNode.left
Pop a node from stack s and set it to currentNode
1. If the popped node has a right child and the right child is at top of stack, then remove the right child from stack, push the currentNode back and set currentNode as currentNode 's right child.
2. Else print currentNode's data and set currentNode as NULL.
Repeat steps 2 and 3 while stack is not empty.

// Iterative solution

public void postorderIter( TreeNode root) {

if( root == null ) return;

Stack<TreeNode> s = new Stack<TreeNode>( );

TreeNode current = root;

while( true ) {

if( current != null ) {

if( current.right != null )

s.push( current.right );

s.push( current );

current = current.left;

continue;

}

if( s.isEmpty( ) )

return;

current = s.pop( );

if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) {

s.pop( );

s.push( current );

current = current.right;

} else {

System.out.print( current.data + " " );

current = null;

}

Lets create java program for postOrder traversal:

100

package org.arpit.java2blog.binarytree;

import java.util.Stack;

public class BinaryTreePostOrder {

public static class TreeNode

{

int data;

TreeNode left;

TreeNode right;

TreeNode(int data)

{

this.data=data;

}

// Recursive Solution

public void postOrder(TreeNode root) {

if(root != null) {

postOrder(root.left);

postOrder(root.right);

//Visit the node by Printing the node data

System.out.printf("%d ",root.data);

}

// Iterative solution

public void postorderIter( TreeNode root) {

if( root == null ) return;

Stack<TreeNode> s = new Stack<TreeNode>( );

TreeNode current = root;

while( true ) {

if( current != null ) {

if( current.right != null )

s.push( current.right );

s.push( current );

current = current.left;

continue;

}

if( s.isEmpty( ) )

return;

current = s.pop( );

if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) {

s.pop( );

s.push( current );

current = current.right;

} else {

System.out.print( current.data + " " );

current = null;

}

public static void main(String[] args)

{

BinaryTreePostOrder bi=new BinaryTreePostOrder();

// Creating a binary tree

TreeNode rootNode=createBinaryTree();

System.out.println("Using Recursive solution:");

bi.postOrder(rootNode);

System.out.println();

System.out.println("-------------------------");

System.out.println("Using Iterative solution:");

bi.postorderIter(rootNode);

}

public static TreeNode createBinaryTree()

{

TreeNode rootNode =new TreeNode(40);

TreeNode node20=new TreeNode(20);

TreeNode node10=new TreeNode(10);

TreeNode node30=new TreeNode(30);

TreeNode node60=new TreeNode(60);

TreeNode node50=new TreeNode(50);

TreeNode node70=new TreeNode(70);

rootNode.left=node20;

rootNode.right=node60;

node20.left=node10;

node20.right=node30;

node60.left=node50;

node60.right=node70;

return rootNode;

}

Run above program and you will get following output:

Using Recursive solution:
10 30 20 50 70 60 40
————————-
Using Iterative solution:
10 30 20 50 70 60 40

Java Binary tree tutorial

Please go through java interview programs for more such programs.

Was this post helpful?

Let us know if you liked the post. That’s the only way we can improve.

Binary Tree PostOrder traversal in java