CareerCup

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

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

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

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