Binary Tree InOrder traversal in java


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

This is 4th part of java binary tree tutorial.

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

InOrder traversal:

In InOrder traversal,each node is processed between subtrees.In simpler words,Visit left subtree, node and then right subtree.
Steps for InOrder traversal are:
  • Traverse the left subtree in InOrder.
  • Visit the node.
  • Traverse the right subtree in InOrder.

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

For recursion, we use implicit stack. So here to convert recursive solution to iterative, we will use explicit stack.
Steps for iterative solution:

  1. Create an empty stack s and Initialize currentNode as root
  2. Push the currentNode to s and set currentNode = currentNode.left until currentNode is NULL
  3. If currentNode is NULL and s is not empty then
    • Pop the top node from stack s and print it
    •  set currentNode = currentNode.right
    • go to step 2
  4. If stack is empty and currentNode is also null then we are done with it

Lets create java program for InOrder traversal:

Run above program and you will get following output:

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

Java Binary tree tutorial

Please go through java interview programs for more such programs.

Add Comment