# Inorder, Preorder, Postorder Traversal | Iterative &#038; Recursive

Written by

studymite

## Recursive Tree Traversal

### Pre-Order Recursive

We first print the data then traverse the left subtree and the right subtree.

### In-Order Recursive

We first traverse the left subtree then print the data and then traverse right subtree.

### Post-Order

We first traverse the left and right subtree then print the data.

``````#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
left = right = NULL;
}
};
void recursiveTraversal(Node* root){
if(root == NULL) return;
cout&lt;&lt;root-&gt;data&lt;&lt;" "; //Pre-order
recursiveTraversal(root-&gt;left);
//cout&lt;&lt;root-&gt;data&lt;&lt;" ";	//In-order
recursiveTraversal(root-&gt;right);
//cout&lt;&lt;root-&gt;data&lt;&lt;" "; //Post-order

}
``````int main() {
/*
1
/
2      3
/   \   /
4     5 6    7
/
struct Node root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->left = new Node(6);
root->right->right = new Node(7);
recursiveTraversal(root);
return 0;
}``````

## Iterative Tree Traversal

### Using map and stack

For iterative traversal, we will take an unordered map and a stack. We will push the nodes to stack one by one and maintain their current state in an unordered map.

There will be three states of a node, its left part, it’s right part, and its data i.e. LRD.

We just need to do a small modification similar to recursive code to achieve inorder, preorder, and postorder iterative traversal.

``````#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
left = right = NULL;
}
};
unordered_map<Node*, int> cnt;
void iterativeTraversal(Node* root){
if(root == NULL) return;
stack<Node*> s;
s.push(root);
while(!s.empty()){
Node* cur = s.top();
if(cur == NULL) {
s.pop();
continue;
}
/*Pre-Order Iterative
if (cnt[cur] == 0) cout &lt;&lt; cur-&gt;data &lt;&lt; " " ;
else if (cnt[cur] == 1) s.push(cur-&gt;left);
else if (cnt[cur] == 2) s.push(cur-&gt;right);
else s.pop();
*/

/*In-Order Iterative
if (cnt[cur] == 0) s.push(cur-&gt;left);
else if (cnt[cur] == 1) cout &lt;&lt; cur-&gt;data &lt;&lt; " " ;
else if (cnt[cur] == 2) s.push(cur-&gt;right);
else s.pop();
*/

/* Post-Order Iterative */
if (cnt[cur] == 0) s.push(cur-&gt;left);
else if (cnt[cur] == 1) s.push(cur-&gt;right);
else if (cnt[cur] == 2) cout &lt;&lt; cur-&gt;data &lt;&lt; " " ;
else s.pop();

cnt[cur]++;
}

}
``````int main() {
/*
1
/
2      3
/   \   /
4     5 6    7
/
struct Node root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->left = new Node(6);
root->right->right = new Node(7);
iterativeTraversal(root);
return 0;
}``````

### Using stack and pair

We can also reduce the extra space used by map by using a stack of pairs. In pair, we will keep Node and its current state.

``````#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
left = right = NULL;
}
};
void iterativeTraversal(Node* root){
if(root == NULL) return;
stack<pair<Node*,int>> s;
s.push({root,0});
while(!s.empty()){
Node* cur = s.top().first;
int state = s.top().second;
s.pop();
if(cur == NULL || state &gt;= 3) {
continue;
}

s.push({cur, state+1});

/*Pre-Order Iterative
if (state == 0) cout &lt;&lt; cur-&gt;data &lt;&lt; " " ;
else if (state == 1) s.push({cur-&gt;left, 0});
else if (state == 2) s.push({cur-&gt;right, 0});
*/

/*In-Order Iterative
if (state == 0) s.push({cur-&gt;left, 0});
else if (state == 1) cout &lt;&lt; cur-&gt;data &lt;&lt; " " ;
else if (state == 2) s.push({cur-&gt;right, 0});
*/

/* Post-Order Iterative */
if (state == 0) s.push({cur-&gt;left, 0});
else if (state == 1) s.push({cur-&gt;right, 0});
else if (state == 2) cout &lt;&lt; cur-&gt;data &lt;&lt; " " ;
}

}
``````int main() {
/*
1
/
2      3
/   \   /
4     5 6    7
/
struct Node root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->left = new Node(6);
root->right->right = new Node(7);
iterativeTraversal(root);
return 0;
}``````