## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Solution in python

``````from collections import deque

def print_tree_zig_zag(root):
level_values = deque()
last_level = 1
frontier = [(root, 1)]
while frontier:
node, current_level = frontier.pop(0)
if current_level != last_level:
l = []
while level_values:
l.append(level_values.popleft())
print 'Level:', last_level, 'Values:', l
last_level = current_level

if node.left:
frontier.append((node.left, current_level+1))
if node.right:
frontier.append((node.right, current_level+1))

if (current_level % 2) == 0:
level_values.appendleft(node.value)
else:
level_values.append(node.value)

l = []
while level_values:
l.append(level_values.popleft())
print 'Level', last_level, 'Values:', l``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a very basic question. I doubt if anyone asks this question in interviews any more.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@anaghakr89 -- this question was asked in a recent phone interview( one that I haven't seen before ).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.