Inorder tree traversal with Recursion in Java

Binary trees have several ways of Traversal. In this tutorial, we will learn the most popular method of traversing a tree which is the Inorder Tree Traversal, also known as LNR (left-node-right) algorithm, which is a method of DFS. As the name suggests, the depth-first search explores tree towards depth before visiting its sibling. We can use the iterative method to solve this problem using stack but in this example, we will use Recursion as it is the simplest way to solve tree based problems. One important property of inorder tree traversal is that if the tree is a binary tree then it prints the nodes of the tree in sorted order.

To traverse a tree in Inorder fashion there are three steps. They are:

• Recursively traverse left child
• Process the parent node
• Recursively traverse right child

Note: If we traverse the right child before the left child then such a traversal is called Reverse Inorder traversal.

In the example above we can see that only after recursively processing the left subtree followed by the node, the right subtree is processed recursively in the end.

 

To implement this in code we create a data structure to store a Binary Tree Node and then we write a function to create a new binary tree node having given value.

class Node
{
  int data;
  Node left, right;
  public Node(int value)
  {
    data = value;
    left = right = null;
  }
}

Code for Inorder Traversal with recursion in Java

class Node
{
  int data;
  Node left,right;
  public Node(int value)
  {
    data = value;
    left = right = null;
  }
};

class InorderTraversal
{
  public static void inorder(Node root)
  {
    if (root == null) 
    {
      return;
    }

    inorder(root.left);
    System.out.print(root.data + " ");
    inorder(root.right);
  }

  public static void main(String[] args)
  {	
    Node root = new Node(40);
    root.left = new Node(20);
    root.right = new Node(50);
    root.left.left = new Node(10);
    root.left.right = new Node(30);
    root.right.left = new Node(55);
    root.right.right = new Node(60);
    
    System.out.print("The inorder traversal for the tree is: ");
    inorder(root);
  }
}

Output:

The inorder traversal for the tree is: 10 20 30 40 55 50 60

Explanation

• Firstly we construct the tree and use the recursive function to perform inorder traversal of the tree.

    The Constructed tree is:

40
/    \
/        \
20          50
/ \            / \
/      \        /      \
10      30  55     60

• If the current node is not empty :
  1. Traverse the left subtree and display the node.
  2. Display the parent node of the left subtree.
  3. Traverse the right subtree and display the node.
• From the example, you can see that as the given tree is a binary tree the nodes are printed in sorted order.

Hope you’ve understood the code 🙂
Any questions please feel free to drop in your comments.

You can also read:

• Postorder tree Traversal using Recursion in Java
• Preorder tree Traversal using Recursion in Java