{"post":"

Level order traversal in Spiral form

We will traverse each level and store all the nodes at that level in a temporary vector. We will keep the current direction in a variable that will change after traversing each level.

#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 levelOrderSpiral(Node* root, int state){\r\nif(!root) return;
\nqueue&lt;Node*&gt;q;\r\nq.push(root);\r\nbool dir = 0;\r\nwhile(!q.empty()){\r\n\tint size = q.size();\r\n  \tvector&lt;Node*&gt; temp;\r\n  \tfor(int i = 0; i &lt; size; i++){\r\n    \tNode* curr = q.front();\r\n      \tq.pop();\r\n      \ttemp.push_back(curr);\r\n      \tif(curr-&gt;left) q.push(curr-&gt;left);\r\n        if(curr-&gt;right) q.push(curr-&gt;right);\r\n    }\r\n  \tif(dir == 0){\r\n    \tfor(auto i:temp) cout&lt;&lt;i-&gt;data&lt;&lt;\" \";\r\n    } else {\r\n    \tfor(int i = temp.size()-1; i &gt;= 0; i--){\r\n        \tcout&lt;&lt;temp[i]-&gt;data&lt;&lt;\" \";\r\n        }\r\n    }\r\n  \tdir = !dir;\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\nlevelOrderSpiral(root, 0);\r\nreturn 0;\r\n}

\n","title":"Level order traversal – Spiral form","authorDetails":{"name":"studymite","slug":"admin"},"description":"Here we will do a level order traversal of a tree in spiral form using breadth first search technique.","slug":"level-order-traversal-spiral-form/","articleId":"636a83417bb1ce5072622b02","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}