Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
What is Inorder Traversal of a Binary Tree?
Algorithm for Inorder traversal without Recursion
Code for Iterative Inorder Traversal in JAVA
Complexity Analysis
Frequently Asked Questions
What are the types of tree traversals you are aware of?
Explain the inorder traversal of a binary tree?
Recommended Problems
Recommended Reading
Last Updated: Mar 27, 2024

Iterative Inorder Traversal of Binary tree

Author Yogesh Kumar
0 upvote
Master Power BI using Netflix Data
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM


Before directly diving into the topic of Iterative Inorder Traversal of Binary tree, let’s cover the basics and have a quick recap, and see what a tree and its type and about preorder traversal. Because then only we will understand the algorithm and intuition behind Inorder Traversal without recursion.

A tree can be defined as a type of data structure that is formed by a collection of nodes. These nodes represent the value and are interconnected via edges.

Following are the defining properties of a tree:

1. The one node from which the entire tree originates is called the root node.

2. Every node can have only 1 parent and multiple children.

3. Root node does not have a parent node.

4. Each node is connected to its child node and vice versa via edge.

Trees can be of the following types:

  1. General Tree: General tree is a type of tree in which there are no restrictions as so to the number of children a node can have
    Example: Family tree, Folder Structure, etc.
  2. Binary Tree: A tree in which every node is allowed to have at most two children. Namely a left node and a right node. Binary trees are further divided into many types based on their application. 
    Full Binary Tree: A tree that has either zero or two children.
    Perfect Binary tree: A tree in which all the interior nodes have two children and all the leaves have the same depth.
  3. Balanced Tree: When the height of the left subtree and the right subtree at any node differ by at most one, then that tree can be called a balanced tree.
  4. Binary Search Tree: A simple binary tree that also contains binary search properties is turned into a binary search tree. Binary search property means that the value of all the nodes in the left subtree should be less than the root node and the values of all nodes in the right subtree is greater than the root node. Further, the left and right subtree must also be a binary search tree. Binary search tree variants are AVL tree, B-Tree, Red-black tree, etc.

What is Inorder Traversal of a Binary Tree?

The left sub-tree comes first, followed by the root node, and then the right subtree. Symmetric traversal is another name for in-order traversal. The in-order algorithm is also known as the LNR traversal algorithm (Left-Node-Right). An in-order traversal algorithm is usually used to display the elements of a binary search tree.

Let us look at an example to understand this:

  1. Traverse to the left subtree
  2. Traverse to the root
  3. Traverse to the right subtree.
binary tree inorder traversal

Source:- Inorder

Recommended: Try the Problem yourself before moving on to the solution

Algorithm for Inorder traversal without Recursion

STEP 1. Let's create an empty stack and call it "S".
STEP 2. Now we shall initialize the current node as the root node.
Step 3. Keep pushing the current node to “S” and set current = current->left until the current becomes NULL
STEP 4. If the current node is null and the stack is not empty then:
a) Pop the top item from the stack.
b) Print the popped item, set current = poppedItem->right 
c) Go to step 3.
STEP 5.  If there is a NULL value in the current and the stack is empty(no more nodes to explore) then we stop.

Code for Iterative Inorder Traversal in JAVA

// inorder traversal without recursion of binary tree
import java.util.Stack;
public class Main 
    public static void main(String[] args) throws Exception 
    	// construct binary tree 
    	TreeToProcess bt = TreeToProcess.create(); 
    	// traversing the binary tree 
    	System.out.println("The nodes for binary tree in their Inorder:"); 
class TreeToProcess 
    static class TreeNode
        String data; TreeNode left, right;
        TreeNode(String value) 
   = value;
            left = right = null; 
        boolean isLeaf()
            return left == null ? right == null : false; 
    TreeNode root; 
    // root of the binary tree
    public void ProcessinOrderWithoutRecursion() 
        Stack<TreeNode> nodes = new Stack<>();
        TreeNode current = root; 
        while (!nodes.isEmpty() || current != null) 
            if (current != null) 
                nodes.push(current); current = current.left;
                TreeNode node = nodes.pop(); 
                System.out.printf("%s ",; current = node.right; 
    // Defining the tree "t" to test the same
    public static TreeToProcess create() 
        TreeToProcess t = new TreeToProcess(); 
        //       4
        //      / \
        //     2   0
        //    / \   \
        //   1   3   6
        //  /       / \
        // 5       7   8

        TreeNode root = new TreeNode("4"); 
        t.root = root; 
        t.root.left = new TreeNode("2"); 
        t.root.left.left = new TreeNode("1"); 
        t.root.left.left.left = new TreeNode("5"); 
        t.root.left.right = new TreeNode("3"); 
        t.root.right = new TreeNode("0"); 
        t.root.right.right = new TreeNode("6"); 
        t.root.right.right.left = new TreeNode("7"); 
        t.root.right.right.right = new TreeNode("8"); 
        return t;     



The nodes for binary tree in their Inorder:
5 1 2 3 4 0 7 6 8 .

Complexity Analysis

Time Complexity: O(n), where n is the total number of nodes in a tree as we are traversing the whole binary tree.

Space Complexity: O(h), where h is the height of the tree due to the space consumed in maintaining the stack. The height of the tree can be n for skewed binary trees, where n is the number of nodes in the binary tree.


You can watch this video for proper conceptual knowledge along with preorder traversal and postorder traversal of a BST.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job

Frequently Asked Questions

What are the types of tree traversals you are aware of?

Unlike other linear data structures, the tree has three ways of traversal:

  • Inorder: Traversal is made from the left node, then root node, and finally the right node.
  • Preorder: Traversal is made from the root node, then left node, and finally the right node.
  • Postorder: Traversal is made from the left node, then right node, and finally the root node.

Explain the inorder traversal of a binary tree?

In inorder traversal we first visit the left child including its entire subtree and then we visit the root node then finally we visit the right child node including its entire subtree.


In this article, we discussed Inorder Traversal without Recursion of Tree with all crucial aspects. We discussed binary trees and Their traversal in detail and implemented the Inorder Traversal without Recursion of a binary tree in Java.

If you want to learn as well as practice coding questions then you can look out for our guided path for DSA which is absolutely free.

Recommended Problems

Recommended Reading


If you want to master tree data structure, it is a critical topic in data structures and algorithms and from an interview point of view, especially in Product-based companies like Amazon, Microsoft, etc. In that case, you can check our blog on mastering trees. Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of Java, etc. as well as some Contests and Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Previous article
Reverse alternate levels of a perfect binary tree
Next article
Morris Traversal Postorder
Live masterclass