{"post":"

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>\nusing namespace std;\nstruct Node{\nint data;\nNode* left;\nNode* right;\nNode(int data){\nthis->data = data;\nleft = right = NULL;\n}\n};
\nvoid recursiveTraversal(Node* root){\nif(root == NULL) return;
\ncout&lt;&lt;root-&gt;data&lt;&lt;\" \"; //Pre-order\nrecursiveTraversal(root-&gt;left);\n//cout&lt;&lt;root-&gt;data&lt;&lt;\" \";\t//In-order\t\nrecursiveTraversal(root-&gt;right);\n//cout&lt;&lt;root-&gt;data&lt;&lt;\" \"; //Post-order\n
\n}
\nint main() {\n/*\n1\n/    
\n2      3\n/   \\   /  
\n4     5 6    7\n/\nstruct Node root = new Node(1);\nroot->left = new Node(2);\nroot->left->left = new Node(4);\nroot->left->right = new Node(5);\nroot->right = new Node(3);\nroot->right->left = new Node(6);\nroot->right->right = new Node(7);\nrecursiveTraversal(root);\nreturn 0;\n}

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>\nusing namespace std;\nstruct Node{\nint data;\nNode* left;\nNode* right;\nNode(int data){\nthis->data = data;\nleft = right = NULL;\n}\n};
\nunordered_map<Node*, int> cnt;\nvoid iterativeTraversal(Node* root){\nif(root == NULL) return;\nstack<Node*> s;\ns.push(root);\nwhile(!s.empty()){\nNode* cur = s.top();\nif(cur == NULL) {\ns.pop();\ncontinue;\n}
\n  /*Pre-Order Iterative\t\n  \tif (cnt[cur] == 0) cout &lt;&lt; cur-&gt;data &lt;&lt; \" \" ;\n    else if (cnt[cur] == 1) s.push(cur-&gt;left);\n    else if (cnt[cur] == 2) s.push(cur-&gt;right);\n    else s.pop();\n  */\n  \n  /*In-Order Iterative\n    if (cnt[cur] == 0) s.push(cur-&gt;left);\n    else if (cnt[cur] == 1) cout &lt;&lt; cur-&gt;data &lt;&lt; \" \" ;\n    else if (cnt[cur] == 2) s.push(cur-&gt;right);\n    else s.pop();\n  */\n  \n  /* Post-Order Iterative */\n  \tif (cnt[cur] == 0) s.push(cur-&gt;left);\n    else if (cnt[cur] == 1) s.push(cur-&gt;right);\n    else if (cnt[cur] == 2) cout &lt;&lt; cur-&gt;data &lt;&lt; \" \" ;\n    else s.pop();\n  \t\n  \tcnt[cur]++;\n}\n
\n}
\nint main() {\n/*\n1\n/    
\n2      3\n/   \\   /  
\n4     5 6    7\n/\nstruct Node root = new Node(1);\nroot->left = new Node(2);\nroot->left->left = new Node(4);\nroot->left->right = new Node(5);\nroot->right = new Node(3);\nroot->right->left = new Node(6);\nroot->right->right = new Node(7);\niterativeTraversal(root);\nreturn 0;\n}

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>\nusing namespace std;\nstruct Node{\nint data;\nNode* left;\nNode* right;\nNode(int data){\nthis->data = data;\nleft = right = NULL;\n}\n};
\nvoid iterativeTraversal(Node* root){\nif(root == NULL) return;\nstack<pair<Node*,int>> s;\ns.push({root,0});\nwhile(!s.empty()){\nNode* cur = s.top().first;\nint state = s.top().second;\ns.pop();
\n  \tif(cur == NULL || state &gt;= 3) { \n      continue; \n    }\n    \n  \ts.push({cur, state+1});\n  \t\n  /*Pre-Order Iterative\t\n  \tif (state == 0) cout &lt;&lt; cur-&gt;data &lt;&lt; \" \" ;\n    else if (state == 1) s.push({cur-&gt;left, 0});\n    else if (state == 2) s.push({cur-&gt;right, 0});\n  */\n  \n  /*In-Order Iterative\n  \tif (state == 0) s.push({cur-&gt;left, 0});\n    else if (state == 1) cout &lt;&lt; cur-&gt;data &lt;&lt; \" \" ;\n    else if (state == 2) s.push({cur-&gt;right, 0});\n  */\n  \n  /* Post-Order Iterative */\n  \tif (state == 0) s.push({cur-&gt;left, 0});\n    else if (state == 1) s.push({cur-&gt;right, 0});\n    else if (state == 2) cout &lt;&lt; cur-&gt;data &lt;&lt; \" \" ;\n}\n
\n}
\nint main() {\n/*\n1\n/    
\n2      3\n/   \\   /  
\n4     5 6    7\n/\nstruct Node root = new Node(1);\nroot->left = new Node(2);\nroot->left->left = new Node(4);\nroot->left->right = new Node(5);\nroot->right = new Node(3);\nroot->right->left = new Node(6);\nroot->right->right = new Node(7);\niterativeTraversal(root);\nreturn 0;\n}

\n","title":"Inorder, Preorder, Postorder Traversal | Iterative & Recursive","authorDetails":{"name":"studymite","slug":"admin"},"description":"We will see inorder preorder and postorder traversal with recursion and with iteration. In iteration we will traverse the tree using a stack.","slug":"inorder-preorder-postorder-traversal-iterative-recursive/","articleId":"636a83417bb1ce5072622b06","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}