How to Implement Binary Tree InOrder traversal in Java without Recursion

I have been writing about different binary tree traversal algorithms and so far we have seen both pre-order and post-order algorithms to traverse a binary tree and today you’ll learn about the in-order or sorted order algorithms. This is actually the second part of implementing the inorder traversal of a binary tree in Java, in the first part, I have shown you how to solve this problem using recursion and in this part, we’ll implement the inorder traversal algorithm without recursion. Now, some of you might argue, why use iteration if the recursive solution is so easy to implement? Well, that’s true, but the iterative solution is often regarded better as they are not prone to StackOverFlowError. Another reason why we are discussing the iterative solution here is because of technical interviews.

If you go to a programming job interview, you will find that the Interviewer will often ask you to solve the same problem using iteration and recursions like the Fibonacci series or the String reversal algorithm. It’s also good for your learning and developing algorithm skills, which is very important for becoming a better programmer.

The in-order algorithm is very similar to the preorder traversal algorithm we have seen earlier, as both are the depth-first algorithm. The only difference between inorder and preorder traversal is the order in which they visit the left subtree, root, and right subtree.

The inorder traversal first explores the left subtree first until it reaches a leaf node, from there it the print value of the node and starts exploring the right subtree of the node. The process continues until all nodes are visited.

One of the worth knowing things about inorder traversal is that it prints all nodes of the tree in sorted order if the given binary tree is a binary search tree. A useful detail to solve many binary tree-based problems.

Though these are not the only way to traverse the tree, you can also use a breadth-first traversal algorithm like level order traversal (see Data Structures and Algorithms: Deep Dive Using Java), which traverses all nodes of a level before moving on to a new level. If you are preparing for Google or Amazon developer interviews, knowing as many algorithms as possible will improve your chances.

Binary Tree InOrder traversal  in Java without Recursion

The steps for inorder traversal will remain the same with recursion and without it. The key is how to use a Stack to convert a recursive algorithm to an iterative one.

Since we need to explore the left tree, we start with the root and continue to push nodes until we reach the leaf node that’s one condition in our loop. When the current becomes null we pop the node, print its values, and start with the right subtree.

Here are the exact steps to implement in-order traversal in a binary tree without recursion

1) Start with current = root
2) loop, until Stack is empty or current, becomes null
3) if the current is not null push current into the stack and current = current.left
4) if the current is null then pop from stack, print the node value, and current = node.right

and here is the Java method to implement the above steps:

public void inOrderWithoutRecursion() {
        Stack<TreeNode> 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;
            }

        }
    }

You can see that the logic is very much similar to an iterative pre-order algorithm with the only thing we are continuing with left subtree first. This algorithm is slightly tougher than the recursive one, which is extremely easy.

If you find coding this algorithm difficult by yourself, maybe it’s time to refresh your knowledge with a good data structure and algorithm courses like Data Structures in Java: An Interview Refresher on Educative, an interactive coding site to learn some useful tricks and fundamentals.

Java Program to traverse the binary tree using InOrder algorithm

Here is our complete Java program to implement iterative inorder traversal in Java. Similar to the iterative PreOrder algorithm we have used the Stack data structure to convert the recursive algorithm to an iterative one, one of the important things every programmer should remember.

We have used the same classes BinaryTree and TreeNode, which are used in earlier exercises. The code for inorder traversal is encapsulated in the inOrderWithoutRecursion() method.

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 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;

    public void inOrderWithoutRecursion() {
        Stack<TreeNode> 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("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.right.right.left = new TreeNode("67");
        tree.root.right.right.right = new TreeNode("78");

        return tree;
    }

}

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

That’s all about how to traverse a binary tree using an in-order traversal algorithm in Java. One of the common use of in-order traversal is to evaluate infix expressions and print nodes in sorted order of binary search tree. If you come across any other good use of an in-order algorithm then please let us know.