CareerCup

USING 2 STACK SOLUTION :::::

public void printZigZag(Node root) {
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    Node current = null;
    s1.push(root);
    int i = 0;
    while (!s1.empty() || !s2.empty()) {
     // while s1 is not empty...keep pushing to s2 and every alternate time, print the push
      while (!s1.empty()) {
        if (i % 2 == 0) {
          System.out.println(s1.peek().iData);
        }
        s2.push(s1.pop());
      }
      while (!s2.isEmpty()) {
        // while s2 is not empty, keep pushing s2 elements children to s1 and also print alternatively
        current = s2.pop();
        if (i % 2 != 0) {
          System.out.println(current.iData);
        }
        if(current.rightChild!=null)s1.push(current.rightChild);
        if(current.leftChild!=null)s1.push(current.leftChild);
      }
      ++i;
    }
  }

You just need to do BFS... maintain a queue and print all childs.
In case of mirror image you need to make sure you put the right child in the queue first.
Code is below...

static void printTreebylevel(TreeNode root,boolean mirror){
		if(root == null)
			return;
		
		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
		list.add(root);
		
		while(list.isEmpty() == false){
			int n = list.size();
			String s = "";
			boolean alternate  = true;
			while(n!=0){
				TreeNode p = (TreeNode) list.remove();
				n--;
				s = s + p.data + " ";
				if(mirror == false){
					if(p.left!=null)
						list.add(p.left);
					if(p.right!=null)
						list.add(p.right);
				}else{
					if(alternate==false){
						if(p.right!=null)
							list.add(p.right);
						if(p.left!=null)
							list.add(p.left);
					}else{
						if(p.right!=null)
							list.add(p.right);
						if(p.left!=null)
							list.add(p.left);
					}
					alternate = !alternate;
				}
					
			}
			System.out.println(s);
		}
		
	}

Here is a good algo for the first part,

puddleofriddles.blogspot.com/2012/01/print-binary-tree-level-by-level-with.html

use a queue and inqueue the node with level information... transverse the tree using the node which we dqueue from tree...
steps 1 : inqueue the root node with level 0... then loop until the queue is empty..
step2 : Dqueue the tail node from queue and inqueue the child of its in the order left then right along with the level as Dqueue_node->level +1.
step 3 : if the level is same as the previously dqueued node then print it and go to nest node in queue else change the line and print it, also increase the previously printed node by 1 ans go to next node in queue.

in other part of question you can use a additional stack to get the mirror image depending on the level as odd and even. I mean to say for odd level if we want to get a image then dqueue the node untill we get the level 1, inqueue the child as left and right then push the value of node in stack. ones the level is complete pop the elements from stake and print it.
In case of even level don't push the node in stake and just print it after inqueing the child's.

@Manan, I doubt that the above solution works.
Because " TreeNode p = (TreeNode) list.remove(); " statement wouldn't ensure that you always referring to internal nodes.
Also this isn't a linear list. It is a tree.

So , if you can elaborate on this solution , it will be good.

I think we just traverse the three and keep track of the level where we are. If the current level is the necessary level => print the content.

What about this? I just use a list of nodes and an alternate variable.

public static void PrintLevelsAlternateMirror(KNode root)
{
	if(root == null)
		return;

	List<KNode> current = new List<KNode>();
	current.Add(root);
	bool alternate = false;

	while(current.Count > 0)
	{
		if(alternate)
		{
			for(int i  = current.Count-1; i >= 0; i--)
{
	Console.Write(current[i].value + “ “);
}
		}
		else
		{
			for(int i  = 0; i < current.Count - 1; i++)
{
	Console.Write(current[i].value + “ “);
}		
}
Console.WriteLine();
		List<KNode> newList = new List<KNode>();
		for(int i = 0; i < current.Count-1; i++)
		{
			if(current[i].left != null)
				newList.Add(current[i].left);
			if(current[i].right != null)
				newList.Add(current[i].right);
		}

		current = newList;
		// swap
		alternate = (alternate) ? false : true;
		
	}
}

#include <deque>
#include <iostream>
using namespace std;

void PrintLevel(TreeNode* root)
{
    if (root == NULL)
         return;
    deque<TreeNode*> q;
    q.push_back(root);
    while (!q.empty()) {
        int n = q.size();
        while (n != 0) {
             TreeNode* p = q.front();
             q.pop_front();
             cout << p->data << " ";
             if (p->left)
                  q.push_back(p->left);
             if (p->right)
                  q.push_back(p->right);
             --n;
         }
         cout << endl;
    }
}

void level_by_traversal_fromtop(struct node* ele)
{
if(ele == NULL)
return ;
if(ele->lptr!=NULL)
{
stack_node *nw = new stack_node();
nw->ptr = ele->lptr;
nw->next = NULL;
if(first == NULL)
first =tail=nw;
else
{
tail->next = nw;
tail =nw;
}
}
if(ele->rptr !=NULL)
{
stack_node *nw = new stack_node();
nw->ptr = ele->rptr;
nw->next = NULL;
if(first == NULL)
first =tail=nw;
else
{
tail->next = nw;
tail =nw;
}
}
cout<<ele->data<<" ";
if(first !=NULL)
{
stack_node *temp =first;
node *nd = first->ptr;
first = first->next;
delete temp;
level_by_traversal_fromtop(nd);
}

}

struct node* mirror(struct node* root)
{
	if(root==NULL)
	{
		return NULL;
	}
	struct node *l,*r;
	l= mirror(root->lptr);
	r= mirror(root->rptr);
	root->lptr = r;
	root->rptr=l;
	return root;
}