## Interview Question

**Country:**United States

This is a simple extension of the BFS:

```
#include <iostream>
#include <queue>
using namespace std;
template <class T>
class TreeNode
{
public:
T data;
TreeNode<T>* parent;
TreeNode<T>* left;
TreeNode<T>* right;
};
TreeNode<int>* SampleTree()
{
TreeNode<int>* t = new TreeNode<int>();
t->data = 1;
t->left = new TreeNode<int>(); t->left->data = 3;
t->right = new TreeNode<int>(); t->right->data = 2;
t->left->left = new TreeNode<int>(); t->left->left->data = 4;
t->left->right = new TreeNode<int>(); t->left->right->data = 5;
return t;
}
void ZigZagTraversal(TreeNode<int>* tree)
{
queue<pair<TreeNode<int>*, bool> > Q;
Q.push(pair<TreeNode<int>*, bool>(tree,false));
while(!Q.empty())
{
pair<TreeNode<int>*, bool> current = Q.front(); Q.pop();
cout<<current.first->data << ' ';
if(current.second) // if from left to right
{
if(current.first->left!=NULL) Q.push(pair<TreeNode<int>*, bool> (current.first->left, false));
if(current.first->right!=NULL) Q.push(pair<TreeNode<int>*, bool> (current.first->right, false));
}
else // if right to left
{
if(current.first->right!=NULL) Q.push(pair<TreeNode<int>*, bool> (current.first->right, true));
if(current.first->left!=NULL) Q.push(pair<TreeNode<int>*, bool> (current.first->left, true));
}
}
cout<<endl;
}
int main(){
ZigZagTraversal(SampleTree());
return 0;
}
```

Instead of using Queues in BFS, we can use stack and at alternate levels flip the order of left child and right child before pushing on the second stack.

```
void printBFSZigzag(TreeNode* root)
{
bool printInReverse = false;
if(root == NULL)
return;
stack<TreeNode*> s1;
s1.push(root);
do
{
stack<TreeNode*> s2;
while(!s1.empty())
{
TreeNode* top = s1.top();
cout << top->val << " ";
if(printInReverse)
{
if(top->right) s2.push(top->right);
if(top->left) s2.push(top->left);
}
else
{
if(top->left) s2.push(top->left);
if(top->right) s2.push(top->right);
}
s1.pop();
}
s1 = s2;
printInReverse = !printInReverse;
}while(!s1.empty());
cout << endl;
}
```

Solution in python

- Fernando August 04, 2017