CareerCup

void zigZagTraversal(struct node *root)
{
	struct node *Stack1[20],*Stack2[20],*temp;
	int top1=-1,top2=-1,LeftToRight=1;
	
	Stack1[++top1]=root;
	
	while(top1>=0 || top2>=0)
	{
		if(LeftToRight)
		{
			while(top1>=0)
			{
				temp=Stack1[top1--];
				printf("%d ",temp->data);
				
				if(temp->left)
					Stack2[++top2]=temp->left;
					
				if(temp->right)
					Stack2[++top2]=temp->right;
			}
			printf("|");
		}
		else
		{
			while(top2>=0)
			{
				temp=Stack2[top2--];
				printf("%d ",temp->data);
				
				if(temp->right)
					Stack1[++top1]=temp->right;
					
				if(temp->left)
					Stack1[++top1]=temp->left;
			}
			printf("|");
		}
		LeftToRight=1-LeftToRight;
	}
}

in binary tree representation

1 has 2 , 3 child nodes

2 has 4 child node

3 has 5 child node

4 has 6, 7 child node

finally 5 has 8 child node

enum EDirec
{ 
   RIGHT = 0,
   LEFT
}

void f(Node* r)
{
   Stack s;
   EDirec d = RIGHT;
   int   cLevel = 1;
   int   cNextLevel = 0;
 
   if (!r) return;

   s.push(r);

   while (!s.empty)      
   {
      Node *cur = q.pop();
      if (cLevel == 0)
      {
         cLevel = cNextLevel;
         cNextLevel = 0;
         d = ~d;
      }
   
      if(d == Right)
      {
         if(cur->left) 
         {
             s.push(cur->left);
             cNextLevel++;
         }

         if(cur->right)  
         {
             s.push(cur->right);
             cNextLevel++;
         }
      }      
      else
      {  
         // reverse enqueue
      }
     
      cLevel--;      
   }
}

One simple way is to print tree in level order but changing the order of printing depending on level.

int count=0;
public void printZigZag() {
int maxDepth = maxDepth(rootNode);
for (int i = 1; i <= maxDepth; i++) {
printLevelOrder(rootNode, i);
count=i;
}
}

public void printLevelOrder(Node node, int level) {
if (node == null) {
return;
}
if (level == 1) {
System.out.println(node.data);

} else {
if (count % 2 == 0) {
printLevelOrder(node.leftChild, level - 1);
printLevelOrder(node.rightChild, level - 1);
}
else
{
printLevelOrder(node.rightChild, level - 1);
printLevelOrder(node.leftChild, level - 1);

}
}
}

I guess this can be modified to to do in O(n) complexity by using queue and stack depending on the level of tree.

void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
int value = 0;
for(i=1; i<=h; i++)
{
printGivenLevel(root, i, value );
value =value ^ 1;;
}
}

void printGivenLevel(struct node* p, int level, int value )
{
if(p == NULL)
return;
if(level == 1)
printf("%d ", p->data);
else if (level > 1)
{
if(value)
{
printGivenLevel(p->left, level-1, value );
printGivenLevel(p->right, level-1, value );
}
else
{
printGivenLevel(p->right, level-1, value );
printGivenLevel(p->left, level-1, value );
}
}
}

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

struct BT
{
	int data;
	BT *left;
	BT *right;
	BT(int newData)
	{
		data = newData;
		left = NULL;
		right = NULL;
	}
};

void ZigzagLevelPrintTree(BT *root)
{
	if(!root)return;
	deque<BT*> contain;
	contain.push_back(root);
	bool leftFirst = false;
	while(contain.size()!= 0)
	{
		int levelSize = contain.size();
		while(levelSize != 0)
		{
			if(!leftFirst)
			{
				BT* treeNode = contain.front();
				cout<<treeNode->data<<" ";
				contain.pop_front();
				if(treeNode->left)
					contain.push_back(treeNode->left);
				if(treeNode->right)
					contain.push_back(treeNode->right);
			}
			else
			{
				BT* treeNode = contain.front();
				cout<<treeNode->data<<" ";
				contain.pop_front();
				if(treeNode->right)
					contain.push_back(treeNode->right);
				if(treeNode->left)
					contain.push_back(treeNode->left);
			}
			levelSize--;
		}
		cout<<endl;
		leftFirst = !leftFirst;
	}
};

int main()
{
	BT *root = new BT(1);
	root->left = new BT(2);
	root->right = new BT(3);
	root->left->left = new BT(4);
	root->right->right = new BT(5);
	root->left->left->left = new BT(6);
	root->right->right->left = new BT(7);
	ZigzagLevelPrintTree(root);


}

This can be solved by using BFS approach. At each level, toggle the order to push nodes into the queue.

Assume you have a BST class with instance fields: left, right, and value. One can solve this by using three different data structures, two queues and one stack. If anyone knows a better solution that conserves more space, let me know.

Idea is to traverse the tree BFS - but the non-trivial part is knowing when you've completed each level. Simple, keep two counters. One for how many are remaining on the level you are currently processing, and one for keeping track of how many more to process in the next level.

The idea is you keep one queue for processing the tree BFS (level order from left to right).

The other queue and stack are used to enqueue and push, repsectively children nodes.

If you have to print from the right (in which the zigzag now goes from right to left), you should push children nodes onto a stack.

If you have to print from the left, you should enqueue children nodes onto a queue.

When you've completed a level, simply iterate though your queue (or stack) and print its value.

static void printZigZag(BST root) {
		Queue<BST> q = new ArrayBlockingQueue(1000);
		Queue<BST> q2 = new ArrayBlockingQueue(1000);
		Stack<BST> s = new Stack();
		q.add(root);
		int currentLevel = 1;
		int nextLevel = 0;
		boolean startLeft = false;
		boolean addRoot = false;
		
		while (!q.isEmpty()) {
			currentLevel--;
			BST current = q.remove();
			
			if (startLeft) {
				if (current.left != null) 
                                       q2.add(current.left);
				if (current.right != null) 
                                       q2.add(current.right);
			} else {
				if (current.left != null) 
                                         s.push(current.left);
				if (current.right != null)
                                         s.push(current.right);
			}
			
			if (current.left != null) {
				q.add(current.left);
				nextLevel++;
			}
			if (current.right != null) {
				q.add(current.right);
				nextLevel++;
			}
			
			if (currentLevel == 0) {
				if (!addRoot) {
					s.push(current); 
					addRoot = true;
				}
				if (startLeft) {
					while (! q2.isEmpty()) {
						System.out.print(q2.remove().value + " ");
					}
				} else {
					while (! s.isEmpty()) {
						System.out.print(s.pop().value + " ");
					}
				}
				startLeft = !startLeft;
				currentLevel = nextLevel;
				nextLevel = 0;
			}
		}		
	}

I think solution is take the root push in stack,pop the stack queue the childs then dQ the childs and push the childs in stack... basically 1 time in stack next in Q,

This should be done in order of N

use two queues to print out in level order, swap the queue in each cycle. Here is the code I tested already:

public void printZigZag(){
		Queue <Node> queue = new LinkedList <Node> ();
		Queue <Node> temp = new LinkedList <Node> ();
		Stack <Node> temp1 = new Stack<Node> ();
		queue.add(root);
		boolean toggle = true;
		while (!queue.isEmpty()){
			Node cur = queue.poll();
			System.out.print(cur.value + ", ");
			if (toggle){
				if (cur.left!=null){
					temp1.push(cur.left);
				}
				if (cur.right!=null){
					temp1.push(cur.right);
				}
			}
			else{
				if (cur.left!=null){
					temp.add(cur.left);
				}
				if (cur.right!=null){
					temp.add(cur.right);
				}
			}

			
			if (queue.isEmpty ()){
				System.out.println("new level");
				while (!temp.isEmpty()){
					queue.add(temp.poll());
				}
				while (!temp1.isEmpty()){
					queue.add(temp1.pop());
				}
				toggle = !toggle;
			}

		}

	}

Is it Correct if we use 2 stack here like this:

// push the root node in stack1 and pop out all the elements in the Stack1 till it becomes empty.
and at the same time push the leaf nodes of the element which is popped out to stack2.
stack1 : 1
stack2 : -

// pop out from stack1 and push the child of 1 to stack2

stack1 : -
stack2 : 2 3
output :1

// pop out from stack2 till it becomes empty and put their child in stack1

stack1 : 5
stack2 : 2
output : 1 3

stack1 : 5 4
stack2 : -
output: 1 3 2

// the same process is repeating till both stack becomes empty

stack1: 5
stack2: 6 7
output : 1 3 2 4

stack1 : -
stack2:6 7 8
output: 1 3 2 4 5

// pop out all elements which is there in the stack2 since it has child stack1 will also be empty.so finally .

stack1 : -
stack2 : -
output :1 3 2 4 5 8 7 6

Note : I am not sure of this idea.Anyone comment about this and discuss about it

just run a loop for the no of lines for odd lines print line in he given order but in case of even lines print in reverse order.
time: O(n)

just run a loop for the no of lines for odd lines print line in he given order but in case of even lines print in reverse order.
time: O(n)

just run a loop for the no of lines for odd lines print line in he given order but in case of even lines print in reverse order.
time: O(n)