# Inorder, Preorder, Postorder Traversal | Iterative & Recursive

Written By -

## 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<<root->data<<" "; //Pre-order
recursiveTraversal(root->left);
//cout<<root->data<<" ";	//In-order
recursiveTraversal(root->right);
//cout<<root->data<<" "; //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 << cur->data << " " ;
else if (cnt[cur] == 1) s.push(cur->left);
else if (cnt[cur] == 2) s.push(cur->right);
else s.pop();
*/

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

/* Post-Order Iterative */
if (cnt[cur] == 0) s.push(cur->left);
else if (cnt[cur] == 1) s.push(cur->right);
else if (cnt[cur] == 2) cout << cur->data << " " ;
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 >= 3) {
continue;
}

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

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

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

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

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;
}``````

Related Posts:

Online Compilers