In this blog we are going to discuss how to implement binary tree inorder traversal without recursion using stack.

How to approach solution for Binary tree inorder traversal without recursion using stack

  • Push all the nodes from root to all root’s left nodes.
  • pop from the stack if stack is not empty, if there is right child in the popped node then
  • push this node and all its left children into the stack.
  • if the stack is empty ,end the iteration.

Let us visualize our steps

step 1:

   (6)
  /  \ 
(8)  (5)
     / \
   (8) (3)

push root to stack and its all left children
stack
(8)
(6)

step 2:

pop stack and check if there is right child

(8) -> there is no right child  output: 8

step 3:

pop stack and check if there is right child

(6) -> there is a right child (5) ; output : 6

Then push right child and its all left children

 (6) 
 / \ 
(8) (5)
    / \
  (8) (3)

stack
(8)
(5)

step 4:

  (6)  
  / \ 
(8) (5) 
    / \ 
  (8) (3)

stack 
(8) 
(5) 

pop stack -- 8  ; output 8 
pop stack -- 5 ; output 5

As there is right child at 5
push 3 in stack
stack
(3)

again pop stack : output 3

now stack is empty , iteration ends

 

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

typedef struct l
{
        struct l* left;
        struct l* right;
        int data;
} Tree;

Tree *node(int data)
{
    Tree *tmp = new Tree();
    tmp->left = NULL;
    tmp->right = NULL;
    tmp->data = data;
    return tmp;
}
void inorder(Tree* root)
{

}
void inorderTraversal(Tree* root)
{
    if (root == NULL) return ;

    Tree* current = root;
    stack<Tree*> s;
    int flag = 0;

    while (!flag)
    {
        while (current != NULL) // Inserting all leftmost nodes
        {
            s.push(current);
            current = current->left;
        }

        if (!s.empty())
        {
            current = s.top();
            cout << current->data<<" ";
            s.pop();
            current = current->right;
        }
        else
            flag = 1;
    }
}

int main()
{
    Tree* root = node(6);
    root->left = node(8);
    root->right = node(5);
    root->right->left = node(8);
    root->right->right = node(3);
    inorderTraversal(root);
    return 0;
}

output:

8 6 8 5 3



Related Contents to follow