Binary Tree PostOrder traversal in java

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

This is 3rd part of java binary tree tutorial.

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:

Iterative solution:
Steps for iterative solution:

  1. Create an empty stack s and set currentNode =root.
  2. while currentNode is not NULL Do following
    1. Push currentNode ‘s right child and then currentNode to stack.
    2. Set currentNode =currentNode .left
  3. Pop an node from stack and set it as root 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 current node back and set currentNode as currentNode ‘s right child.
    2. Else print currentNode ‘s data and set currentNode as NULL.
  4. Repeat steps 2 and 3 while stack is not empty.

Lets create java program for InOrder traversal:

Run above program and you will get following output:

Java Binary tree tutorial:

Please go through java interview programs for more such programs.

One Response

  1. Max March 20, 2016

Add Comment