Perform InOrder traversal on a Binary Tree by without Recursion

Question:

Given a binary tree root node, perform In Order traversal by using stacks.

Example:

Consider the image given below:

InOrder Traversal (Left, Root, Right): 7 10 15 16 18 25 30

Now lets see how to perform In Order Traversal: (Left, Root, Right)

In In-Order traversal, first Left node will be printed, then root node then the right node.

If we have only one node as below, we print that node.

If we have a tree with 3 nodes as below:

Pass 1:

First we will insert all the nodes at its left into the stack using the first while loop

Stack = 16, 10

Then we will pop the node and print it. We check if “node 10” has right node. If right node is present, the we perform the same operation.
As we dont have right node, we just display 10.

Stack = 16
Display = 10

Pass 2:

Again we pop the top node i.e “node 16” and print the value. Now we check if it has a right node. Yes, it has “node 25” to it’s right.
We push that node into the stack.

Stack = 25
Display = 10, 16

Pass 3:

Again we pop the top node i.e “node 25” and print the value. Now we check if it has a right node. No it doesnt.

Stack =
Display = 10, 16, 25

Hence In-Order Traversal.

Solution in C++

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

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

void print_in_order(struct Node *root) 
{ 
    stack<Node *> s; 

    while (root != NULL) 
    { 
        s.push(root); 
        root = root->left; 
    } 

    while (s.empty() ==  false) 
    {   
        Node *curr = s.top(); 
        cout<<curr->data <<" ";
        s.pop(); 

        if(curr->right != NULL) 
        {
            Node *temp = curr->right; 

            while(temp != NULL) 
            {
              s.push(temp);
              temp = temp->left;
            }
        }
    } 
} 


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    cout<<"In Order Traversal(Left, Root, Right) = " ; print_in_order(root); cout<<endl; 


    return 0;  
}  

Output:

In Order Traversal(Left, Root, Right) = 7 10 15 16 18 25 30