Inorder, Preorder, Postorder Traversal | Iterative & Recursive
Track completion, mastery, and revision.
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;
}
int main() {
/*
1
/
2 3
/ \ /
4 5 6 7
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;
}
}
int main() {
/*
1
/
2 3
/ \ /
4 5 6 7
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();
}
int main() {
/*
1
/
2 3
/ \ /
4 5 6 7
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;
}Finished reading?