InOrder traversal in binary tree without recursion in Java

This is the second part of implementing 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 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 iterative solution here is because of technical interviews. If you to go to a programmer job interview, you will find that Interviewer will often ask you to solve the same problem using iteration and recursion e.g. Fibonacci series or String reversal algorithm. It's also good for your learning and developing algorithm skill, 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 on which they visit left subtree, root, and right subtree. The inorder traversal first explores left subtree until it reaches a leaf node, from their it print value of the node and starts exploring right subtree of the node. The process continues until all nodes are visited.

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

Though these are not the only way to traverse the tree, you can also use breadth-first traversal algorithm e.g. level order traversal (see Introduction to Algorithms), which traverses all nodes of a level before moving on to 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 without Recursion

The steps for inorder traversal will remain same with recursion and without it. The key is how to use a Stack to convert recursive algorithm to an iterative one. Since we need to explore left tree, we start with root and continue to push nodes until we reach the leaf node that's one condition in our loop. When current becomes null we pop the node, print its values and start with right subtree. Here are the exact steps

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

and here is the Java function to implement 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 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 book like Algorithm Design manual.


InOrder traversal in binary tree without recursion in Java



Java Program to traverse 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 Stack to convert recursive algorithm to an iterative one. We have used same classes BinaryTree and TreeNode, which is 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 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 in-order algorithm then please let us know.


Other Binary tree tutorials in Java for Programmers
  • How to implement pre-order traversal in Java?  (solution)
  • How to traverse a binary tree in pre-order without using recursion? (solution)
  • How to implement in-order traversal in Java without recursion? (solution)
  • How to implement linked list using generic in Java? (solution)
  • How to find the middle element of linked list using single pass? (solution)
  • How to find the 3rd element from the end of linked list in Java? (solution)
  • How to reverse a singly linked list in Java? (solution)
  • 5 Books to prepare data structure and algorithm for programming/coding interviews (list)


References
Binary tree data structure
Tree traversal algorithm



2 comments:

  1. Correction in sentence needed: "The inorder traversal first explores right subtree until it reaches a leaf node, from their it print value of the node and starts exploring right subtree of the node." The inorder traversal first explores left subtree until it reaches a leaf node, from there it...

    ReplyDelete
    Replies
    1. Good catch @Anonymous, Thanks, I'll update it.

      Delete