Hello guys, I have been teaching you about different 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 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

The inorder traversal first explores the left subtree 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 given binary tree is 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

##

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 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 function to implement the above steps:

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

##

Here is our complete Java program to implement iterative inorder traversal in Java. Similar to the iterative PreOrder algorithm we have used the

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

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.

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Introduction to Algorithms

Data Structures in Java 9 by Heinz Kabutz

Grokking the Coding Interview: Patterns for Coding Questions

Cracking the Coding Interview - 189 Questions and Solutions

Other

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 on which they visit the left subtree, root, and right subtree.The inorder traversal first explores the left subtree 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 given binary tree is 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 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 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 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 function 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

**Algorithms and Data Structures - Part 1 and 2**on Pluralsight 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 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; } }Outputprinting 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.

**Further Learning**Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Introduction to Algorithms

Data Structures in Java 9 by Heinz Kabutz

Grokking the Coding Interview: Patterns for Coding Questions

Cracking the Coding Interview - 189 Questions and Solutions

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 a linked list using generics in Java? (solution)
- How to find the middle element of linked list using a single pass? (solution)
- How to find the 3rd element from the end of a 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)
- How to implement a binary search tree in Java? (program)
- How to implement in-order traversal in Java? (solution)
- How to implement in-order traversal in Java without recursion? (solution)
- 5 Free Data Structure and Algorithms Courses for Programmers (courses)
- 10 Algorithms Books Every Programmer Should Read (books)
- How to print duplicate elements of an array in Java? (solution)
- How to reverse an array in place in Java? (solution)
- How to reverse a singly linked list in Java? (solution)
- 50+ Data Structure and Algorithms Problems from Interviews (questions)
- 10 Free Data Structure and Algorithm Courses for Programmers (courses)
- 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this binary tree tutorial then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

**P. S.**- If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the**Easy to Advanced Data Structures**course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.
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...

ReplyDeleteGood catch @Anonymous, Thanks, I'll update it.

DeleteThe diagram is misleading for the tree.

ReplyDelete40

/ \

/ \

20 50

/ \ \

10 30 60

/ / \

5 67 78