In-Order Binary Tree Traversal in Java

The inOrder traversal is one of the three most popular ways to traverse a binary tree data structure, the other two being the preOrder and postOrder. During the in-order traversal algorithm, the left subtree is explored first, followed by root, and finally nodes on the right subtree.

You may also like: Binary Searching in Java Without Recursion

You start traversal from the root; then, it goes to the left node, and then again, it goes to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it visited and it moves to the right subtree. Continuing the same algorithm until all nodes of the binary tree are visited, the inOrder traversal is also known as left-node-right or left-root-right traversal or LNR traversal algorithm.

Similar to the preOrder algorithm, it is also a depth-first algorithm because it explores the depth of a binary tree before exploring siblings. Since it is one of the fundamental binary tree algorithms, it's quite popular in programming interviews.

These traversal algorithms are also the basis for learning more advanced binary tree algorithms. Hence, every programmer should learn, understand, and know how to implement in-order and other traversal algorithms.

The easiest way to implement the inOrder traversal algorithm in Java or any programming language is by using recursion. Since the binary tree is a recursive data structure, recursion is the natural choice for solving a tree-based problem. The inOrder() method in the BinaryTree class implements the logic to traverse a binary tree using recursion.

InOrder traversal is extremely important because it also prints nodes of a binary search tree in the sorted order, but only if the given tree is a binary search tree. If you remember, in BST, the value of nodes in the left subtree is lower than the root, and values of the nodes in the right subtree are higher than the root. The inOrder traversal literally means IN order, i.e notes are printed in the order or sorted order.

Even though these three algorithms (pre-order, in-order, and post-order) are popular binary tree traversal algorithms, they are not the only ones. You also have other breadth-first ways to traverse a binary tree, e.g. the level-order traversal.

How to Implement the InOrder Traversal of a Binary Tree

The recursive algorithm of inOrder traversal is very simple. You just need to call the inOrder() method of the BinaryTree class in the order you want to visit the tree. What is most important is to include the base case, which is key to any recursive algorithm.

For example, in this problem, the base case is you reach to the leaf node and there is no more node to explore. At that point in time, recursion starts to wind down. Here are the exact steps to traverse the binary tree using inOrder traversal:

1. Visit left node
2. Print value of the root
3. Visit right node\ and here is the sample code to implement this algorithm using recursion in Java:

private void inOrder(TreeNode node) {
    if (node == null) {
      return;
    }

    inOrder(node.left);
    System.out.printf("%s ", node.data);
    inOrder(node.right);
}

Similar to the preOrder() method in the last example, there is another inOrder() method that exposes inorder traversal to the public and calls this private method, which actually performs the InOrder traversal.

This is the standard way to write a recursive method that takes input; it makes it easier for a client to call the method.

public void inOrder() {
    inOrder(root);
}

You can see that we start with root and then perform a recursive call to the inOrder() method with node.left, which means we are going down on left subtree until we hit node == null, which means the last node was a leaf node.

At this point in time, the inOrder() method will return and execute the next line, which prints the node.data. After that, it's again a recursive inOrder() call with node.right, which will initiate the same process again.

InOrder Traversal of a Binary Tree in Java

Here is our complete solution of the InOrder traversal algorithm in Java. This program uses a recursive algorithm to print the value of all nodes of a binary tree using InOrder traversal.

As I have told you before, during in-order traversal, the value of left subtree is printed first, followed by root and right subtree. If you are interested in the iterative algorithm, you can further check this tutorial of implementing in order traversal without recursion.

import java.util.Stack;

/*
 * Java Program to traverse a binary tree
 * using inorder traversal without recursion.
 * In InOrder traversal first left node is visited, followed by root
 * and right node.
 *
 * input:
 *      40
 *     /\
 *    20   50
 *   / \\
 *  10  30   60
 * /   /\
 * 5  67  78
 *
 * output: 5 10 20 30 40 50 60 67 78
 */

public class Main {

  public static void main(String[] args) throws Exception {

    // construct the binary tree given in question
    BinaryTree bt = BinaryTree.create();

    // traversing binary tree using InOrder traversal using recursion
    System.out
        .println("printing nodes of binary tree on InOrder using recursion");

    bt.inOrder();
  }

}

class BinaryTree {
  static class TreeNode {
    String data;
    TreeNode left, right;

    TreeNode(String value) {
      this.data = value;
      left = right = null;
    }

  }

  // root of binary tree
  TreeNode root;

  /**
   * traverse the binary tree on InOrder traversal algorithm
   */
  public void inOrder() {
    inOrder(root);
  }

  private void inOrder(TreeNode node) {
    if (node == null) {
      return;
    }

    inOrder(node.left);
    System.out.printf("%s ", node.data);
    inOrder(node.right);
  }

  /**
   * Java method to create binary tree with test data
   *
   * @return a sample binary tree for testing
   */
  public static BinaryTree create() {
    BinaryTree tree = new BinaryTree();
    TreeNode root = new TreeNode("40");
    tree.root = root;
    tree.root.left = new TreeNode("20");
    tree.root.left.left = new TreeNode("10");
    tree.root.left.left.left = new TreeNode("5");

    tree.root.left.right = new TreeNode("30");
    tree.root.right = new TreeNode("50");
    tree.root.right.right = new TreeNode("60");
    tree.root.left.right.left = new TreeNode("67");
    tree.root.left.right.right = new TreeNode("78");

    return tree;
  }

}


Output
printing nodes of binary tree on InOrder using recursion
5 10 20 30 67 78 40 50 60

That's all for now on how you can implement the inOrder traversal of a binary tree in Java using recursion. You can see the code is pretty much similar to the preOrder traversal with the only difference in the order we recursive call the method. In this case, we call inOrder(node.left)  first and then print the value of the node.

It's worth remembering that the inOrder traversal is a depth-first algorithm and prints the tree node in sorted order if given binary tree is a binary search tree.

In the next part of this article, I'll share inOrder traversal without recursion. Stay tuned!

Further Reading

Binary Searching in Java Without Recursion

How to Create a Binary Search Tree