CareerCup

private static void zigZagTraversal(BinaryTreeNode root) {
		int leftToRight=1;
		BinaryTreeNode temp;
		Stack<BinaryTreeNode> currentLevel=new Stack<BinaryTreeNode>();
		Stack<BinaryTreeNode> nextLevel=new Stack<BinaryTreeNode>();
		
		System.out.println("Zig Zag Traversal");
		currentLevel.push(root);
		while (!currentLevel.isEmpty()) {
			temp = currentLevel.pop();
			if(temp!=null)
			{
				System.out.println(temp.getData());
				if(leftToRight==1)
				{
					if (temp.getLeft() != null)
						nextLevel.push(temp.getLeft());
					if (temp.getRight() != null)
						nextLevel.push(temp.getRight());
				}
				else
				{
					if (temp.getRight() != null)
						nextLevel.push(temp.getRight());
					if (temp.getLeft() != null)
						nextLevel.push(temp.getLeft());
				}
				
			}
			if(currentLevel.isEmpty())
			{
				leftToRight=1-leftToRight;
				while(!nextLevel.isEmpty())
				{
					currentLevel.push(nextLevel.pop());
				}
			}
			
			
		}
	}

public List<Node> getOrderedNodes(Node rootNode) {
        
        List<Node> result = new LinkedList<Node>();
        
        Stack<Node> currentLevel = new Stack<Node>();
        Stack<Node> nextLevel = new Stack<Node>();
        currentLevel.push(rootNode);
        
        boolean isLeftToRight = true;
        
        while( !currentLevel.isEmpty() ){
            Node currentNode = currentLevel.pop();
            
            if( currentNode != null ){
                result.add(currentNode);
                
                if(isLeftToRight){
                    nextLevel.push(currentNode.getLeft());
                    nextLevel.push(currentNode.getRight());
                }else{
                    nextLevel.push(currentNode.getRight());
                    nextLevel.push(currentNode.getLeft());
                }
            }
            
            if(currentLevel.isEmpty()){
                isLeftToRight = !isLeftToRight;
                Stack<Node> temp = currentLevel;
                currentLevel = nextLevel;
                nextLevel = temp;
            }           
        }
        
        return result;
    }

Can you please provide an example to explain the question?

Do level order traversal inserting nodes in an array with every odd level elements inserted in reverse order.

just like a normal level order traversal..maintain a queue. Use some extra variable to track, how elements are to be printed viz. for even level they be printed in the same sequence they are present in queue and for odd level they are printed in reverse order.

void func(struct node *ptr)
{
     if(ptr==NULL)
     return;
     int n;
     n=numNodes(ptr);
     struct node *arr[n]={NULL}; //n is the number of nodes in tree..initialize array to NULL
     int cl,nl,level,count,index,p,q,i;
     arr[0]=ptr;
     nl=count=index=0;
     p=q=0;
     cl=1;
     while(arr[index]!=NULL)
     {
                            if(level==0)
                            printf("%d",arr[0]->num);
                            cl--;
                            if(arr[index]->left!=NULL)
                            {
                                                   arr[++count]=ptr->left;
                                                   nl++;
                            }
                            if(arr[index]->left!=NULL)
                            {
                                                   arr[++count]=ptr->right;
                                                   nl++;
                            }
                            if(cl==0)
                            {
                                     p=q;
                                     q=index;
                                     cl=nl;
                                     nl=0;
                                     if(!(level%2))   //even level
                                     {
                                                      i=p+1;
                                                      while(i<=q)
                                                      {
                                                                 printf("%d",arr[i]->num);
                                                                 i++;
                                                      }
                                     }
                                     else             //odd level
                                     {
                                                      i=q;
                                                      while(i>p)
                                                      {
                                                                printf("%d",arr[i]->num);
                                                                 i--;
                                                      }
                                     }
                                     level++;
                            }
                            index++;
     }
}