Inorder Traversal in Binary Tree in Java

 What is Inorder Traversal?

Inorder traversal is one of the method of traversing  a binary tree. In inorder traversal, the left subtree is visited first, then the root and later the right sub-tree.In case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order.  In this article inorder is performed using recursion. Other ways of traversing a tree are -:

Inorder traversal in a binary tree in Java

Inorder Traversal Example

Example for Inorder tracersal in a binary tree in Java

Steps to find inorder Traversal

Here are some of the steps for tree traversal :-
  • Step 1: Traverse the left most child which is 4 in above example and print it.
  • Step 2: Then print it’s parent which is 2 and look for the right child.
  • Step3: Then move to right child and print it i.e. print 5
  • Step 4: Print 1 which is the root  and move to it’s right subtree.
  • Step 5: At last print 3 and as all the nodes get visited , so stop. Therefore ,  the printing sequence will be 4 2 5 1 3 .

Algorithm to Find Inorder Traversal using recursion

   Algorithm inorder(tree)

  1.   Recursively traverse left subtree.
  2.   Visit root node.
  3.   Recursively traverse right subtree.

CODE FOR INORDER TRAVERSAL USING RECURSION

//Inorder Traversal in java

/* Node class with left and right child and  current node and key value*/
class Node
{
   Node left ,right;
   int value;
   Node(int value) 
   {
       this.value=value;
       left=null;
       right=null;
   }
}
class Inorder
{
   Node root;  //root of the binary tree
   Inorder()
   {
       root=null;
   }
   /*inorder traversal of binary tree */
   public void inorder(Node ptr)
   {
       if(ptr==null)
       return ;
       /*first traverse left child */
       inorder(ptr.left);
       /*then print the value of node */
       System.out.print(ptr.value);
       /* now traverse the right child */
       inorder(ptr.right);
   }
   public static void main(String[] args)
   {
       Inorder t=new Inorder();
       t.root=new Node(1);
       t.root.left=new Node(2);
       t.root.right=new Node(3);
       t.inorder(t.root);
   }
}

 

Output:

2 1 3

TIME AND SPACE COMPLEXITY TO FIND INORDER TRAVERSAL IN BINARY TREE

Time Complexity

O (n)

Space Complexity

O(h)