Level order traversal – Spiral form

Written by

studymite

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>
using namespace std;

struct Node{ int data; Node* left; Node* right; Node(int data){ this->data = data; left = right = NULL; } };

void levelOrderSpiral(Node* root, int state){ if(!root) return;

queue&lt;Node*&gt;q;
q.push(root);
bool dir = 0;
while(!q.empty()){
	int size = q.size();
  	vector&lt;Node*&gt; temp;
  	for(int i = 0; i &lt; size; i++){
    	Node* curr = q.front();
      	q.pop();
      	temp.push_back(curr);
      	if(curr-&gt;left) q.push(curr-&gt;left);
        if(curr-&gt;right) q.push(curr-&gt;right);
    }
  	if(dir == 0){
    	for(auto i:temp) cout&lt;&lt;i-&gt;data&lt;&lt;" ";
    } else {
    	for(int i = temp.size()-1; i &gt;= 0; i--){
        	cout&lt;&lt;temp[i]-&gt;data&lt;&lt;" ";
        }
    }
  	dir = !dir;
}

}

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); levelOrderSpiral(root, 0); return 0; }