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