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