An **iterative [inorder](https://www.educative.io/answers/what-is-in-order-traversal) traversal of a binary tree** is done using the stack data structure. 

# Algorithm

- Initialize an empty stack.
- Push the current node (starting from the root node) onto the stack. Continue pushing nodes to the left of the current node until a NULL value is reached.
- If the current node is NULL and the stack is not empty:
  
  1. Remove and print the last item from the stack.
  2. Set the *current* node to be the node to the *right* of the *removed* node.
  3. Repeat the second step of the algorithm.
- If the current node is NULL ​and the stack is empty, then the algorithm has finished.

The algorithm is illustrated on a sample binary tree below:


#include <iostream>
#include <stack>
using namespace std;

struct Node 
{ 
    int data; 
    struct Node* left; 
    struct Node* right; 
    Node (int data) 
    { 
        this->data = data; 
        left = right = NULL; 
    } 
}; 

void inOrderTraversal(Node *root)
{
	// Create an empty stack.
	stack<Node*> stack;

	// Start from the root node.
	Node *curr = root;

	// If the current node is null and stack is also empty, the algorithm terminates.
	while (!stack.empty() || curr != NULL)
	{
    // Push the current node to the stack and set current=current->left.
		if (curr != NULL)
		{
			stack.push(curr);
			curr = curr->left;
		}
		else // If the curr node is NULL.
		{
			curr = stack.top(); 
			stack.pop(); // Pop the node on top of stack.
			cout << curr->data << " "; // Print it.
			curr = curr->right; 
		}
	}
}

// Driver code
int main() {
    struct Node *root = new Node(1); 
    root->left        = new Node(2); 
    root->right       = new Node(3); 
    root->left->left  = new Node(4); 
    root->left->right = new Node(5); 
    inOrderTraversal(root);
  return 0;
}

import java.util.Stack; 

class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 

@SuppressWarnings("unchecked")
class BinaryTree
{
    Node root;
    public static void inOrderTraversal(Node root)
    {
      Stack<Node> stack = new Stack();
      Node curr = root;
      while (!stack.empty() || curr != null)
      {
        if (curr != null)
        {
          stack.push(curr);
          curr = curr.left;
        }
        else
        {
          curr = stack.pop();
          System.out.print(curr.data + " ");
          curr = curr.right;
        }
      }
    }

    public static void main( String args[] )
    {
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(1); 
        tree.root.left = new Node(2); 
        tree.root.right = new Node(3); 
        tree.root.left.left = new Node(4); 
        tree.root.left.right = new Node(5); 
        tree.inOrderTraversal(tree.root); 
    }
}

Java

How to perform an iterative inorder traversal of a binary tree

An iterative inorder traversal of a binary tree is done using the stack data structure. Algorithm   Initialize an empty stack.   Push the current node (starting from the root node) onto the stack. Continue pushing nodes to the left of the current node until a NULL value is reached.   If the current node is NULL and the stack is not empty:  Remove and print the last item from the stack. Set the current node to be the node to the right of the removed node. Repeat the second step of the algorithm.    If the current node is NULL ​and the stack is empty, then the algorithm has finished.   The algorithm is illustrated on a sample binary tree below: 

How to perform an iterative inorder traversal of a binary tree

Algorithm

Implementation