• • 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