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