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<Node*>q;
  	q.push(root);
  	bool dir = 0;
  	while(!q.empty()){
    	int size = q.size();
      	vector<Node*> temp;
      	for(int i = 0; i < size; i++){
        	Node* curr = q.front();
          	q.pop();
          	temp.push_back(curr);
          	if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
        }
      	if(dir == 0){
        	for(auto i:temp) cout<<i->data<<" ";
        } else {
        	for(int i = temp.size()-1; i >= 0; i--){
            	cout<<temp[i]->data<<" ";
            }
        }
      	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;
}

Report Error/ Suggestion

Related Posts:









CopyRight © 2020

CopyRight © 2020