Level order traversal – Spiral form
Written by
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; }