Inorder, Preorder, Postorder Traversal | Iterative & 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; }