InOrder traversal of Binary tree in Java using Recursion and Iteration - Example Tutorial

This is the second article about tree traversal algorithms using Java. In the first part, we have seen the pre-order algorithm for visiting all nodes of the binary tree and today we'll learn about the InOrder traversal. As I told you before, unlike array and linked list, the binary tree has several ways of traversal. The traversal algorithms are broadly divided into depth-first and breadth-first traversal algorithms depending upon how the algorithm actually works. As the name suggests, depth-first explores binary tree towards depth before visiting sibling, while breath first visits all nodes in the same level before going to next level, hence it is also known as level order traversal. 

Both PreOrder and InOrder tree traversal algorithms are depth-first and the only difference between pre-order and in-order algorithms is the order on which root, left node, and right node of the binary tree is visited.

The In order traversal algorithm first visits the left node, followed by root, and finally right node. This is different than pre-order traversal which visits the root first. One of the important properties of inorder traversal is that it prints the nodes in sorted order if the given binary tree is a binary search tree.

Remember, a binary tree is called a binary search tree if all nodes in the left subtree are lower than the root and all nodes in the right subtree are greater than the root. To learn more about the binary search tree, I suggest you read a good book on Data structure and algorithms like Introduction to Algorithms by Thomas H. Cormen.

In our example, I have also used a binary search tree to demonstrate that the InOrder tree traversal prints nodes of a binary tree in sorted order. Continuing the tradition, I have shared both recursive and iterative solutions to this problem.

This is extremely important from the interview point of view. Even though the recursive solution is easier, takes fewer lines of code, and it's more readable, you should know how to traverse a binary tree without recursion in Java to do well on programming interviews.

Before going for a programming/coding interview, It's absolutely necessary to do as much practice in data structure and algorithms as possible to take advantage of all the knowledge available. You can also join a comprehensive Data Structure and Algorithms course on Udemy to fill the gaps in your understanding.

Binary tree InOrder traversal in Java - Recursion

If you have solved a couple of binary tree problems e.g. finding all leaf nodes, then you know that recursion is the best way to solve the tree based problems. Since the binary tree is a recursive data structure, recursion fits them naturally. Here are the steps to visit a binary tree on InOrder:

1) visit left node
2) visit root
3) visit right node

To implement this algorithm, you can write a method to traverse all nodes of binary tree using InOrder traversal by following steps:

1. Write a method inOrder(TreeNode node)
2. Check if node == null, if yes then return, this is our base case. 
3. Call the inOrder(node.left) to recursively visit left subtree
4. Print value of the node
5. Call the inOrder(node.right) to recursively traverse the right subtree. 

This will print all nodes of a binary tree as per the In order traversal. If a binary tree is a binary search tree, then all nodes of the tree will be printed in sorted order. Here is a method to implement in order algorithm in Java:

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

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

The method is made private because it is exposed via another public method inOrder() which doesn't expect a parameter from the client. This is an example of a facade pattern that makes the method simpler for the client. The recursive algorithm is simple to understand, you go deep on the left subtree until you find the leaf node. 

Once you find that, the recursive stack starts to unwind and it prints node data and starts to explore the right subtree. See Head First design patterns to learn more about facade patterns in Java.

Here is another example of Inorder traversal of binary tree:

InOrder traversal of Binary tree in Java - Iterative 

As we did with the iterative pre-order algorithm, you can use a Stack to convert the recursive in order algorithm to an iterative one. Of course, the solution without recursion is not that easy to read but not very difficult to understand. We start with the root and process until current node is not or Stack is not empty. 

We start pushing nodes from left subtree until we reach to a leaf node. At that point, we pop() the last element, print its value and starts exploring right subtree by assigning current = current.right. This continues until our stack becomes empty, at that point, the tree traversal is finished and all elements of the binary tree is visited.

Let's visit the following binary tree using InOrder traversal using our iterative Java algorithm:

    4
   / \
  2   5
 / \   \
1   3   6 

public void inOrderWithoutRecursion() {
    Stack nodes = new Stack<>();
    TreeNode current = root;

    while (!nodes.isEmpty() || current != null) {

      if (current != null) {
        nodes.push(current);
        current = current.left;
      } else {
        TreeNode node = nodes.pop();
        System.out.printf("%s ", node.data);
        current = node.right;
      }

    }
  }
Output
1 2 3 4 5 6 

Since are printing elements on inorder traversal and our binary tree is a binary search tree, you can see they are printed in sorted order. See Algorithms design manual by Steve S, Skiena to learn more about different types of tree traversal algorithm e.g. level order traversal.

Java Program to traverse a binary tree using InOrder Algorithm

Here is our complete program to implement in order traversal of a binary tree in Java. This is similar to the preOrder example we have seen earlier, with the only difference that root is visited second instead of first. The recursive algorithm is straightforward but the iterative one is a little bit difficult to understand. 

You must remember that Stack is a LIFO data structure and the node you push first will be popped later. Since you need to visit the node in left-node-right order, you have to push nodes of left tree until you reach the leaf node. Thereafter you print the value and start exploring right subtree.

We have used the same BinaryTree and TreeNode class, which is used to represent a binary tree in earlier tree based problems e.g. counting leaf nodes. The BinaryTree is your regular binary tree and TreeNode represents a node in the binary tree.

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:
 *     4
 *    / \
 *   2   5
 *  / \   \
 * 1   3   6
 * 
 * output: 1 2 3 4 5 6 
 */

public class InOrderTraversal {

  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 a binary tree on InOrder using recursion");

    bt.inOrder();

    System.out.println(); // insert new line

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

}

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

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

    boolean isLeaf() {
      return left == null ? right == null : false;
    }

  }

  // 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);
  }

  public void inOrderWithoutRecursion() {
    Stack nodes = new Stack<>();
    TreeNode current = root;

    while (!nodes.isEmpty() || current != null) {

      if (current != null) {
        nodes.push(current);
        current = current.left;
      } else {
        TreeNode node = nodes.pop();
        System.out.printf("%s ", node.data);
        current = 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("4");
    tree.root = root;
    tree.root.left = new TreeNode("2");
    tree.root.left.left = new TreeNode("1");

    tree.root.left.right = new TreeNode("3");
    tree.root.right = new TreeNode("5");
    tree.root.right.right = new TreeNode("6");

    return tree;
  }

}

Output
printing nodes of a binary tree on InOrder using recursion
1 2 3 4 5 6 
printing nodes of a binary tree on InOrder using iteration
1 2 3 4 5 6 

That's all about how to visit all nodes of a binary tree using the InOrder traversal algorithm. As I said before, InOrder is a depth-first traversal algorithm, and the left subtree is explored first before visiting root and the right subtree is explored last, hence it is also known as LNR (left-node-right) algorithm. 

Related Data Structure and Algorithms tutorials for Java Programmers

• Sieve of Eratosthenes algorithm to generate prime numbers (algorithm)
• How to find GCD and LCM of two numbers in Java? (solution)
• How to find if a linked list contains a cycle in Java? (solution)
• How to find the 3rd node from last in a linked list in Java? (solution)
• How to find duplicate elements in the given array? (solution)
• How to reverse an array in place in Java? (solution)
• How to find the length of the linked list in one pass? (solution)
• 5 books to learn Data structure and Algorithms? (list)

P. S. - There is one more unique property of inorder traversal, it prints nodes in sorted order if the given binary tree is a binary search tree. So, you can use this algorithm if you have to print all nodes in sorted order of a BST.