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

Use a stack to perform iterative inorder traversal by processing nodes left-to-right until all nodes are visited and printed.

How to perform an iterative inorder traversal of a binary tree

Algorithm

Implementation