CareerCup

Using Two Stacks is the answer

public static void printZigZag(BTNode root, boolean leftToRight)
	{
		Stack<BTNode> currentStack, nextStack;
		currentStack = new Stack<BTNode>();
		nextStack = new Stack<BTNode>();
		if(root == null)
			return;
		currentStack.push(root);
		while(!currentStack.isEmpty())
		{
			BTNode node = currentStack.pop();
			System.out.println(node.data);
			if(leftToRight)
			{
				if(node.right != null)
					nextStack.push(node.right);
				if(node.left != null)
					nextStack.push(node.left);
			}
			else
			{
				if(node.left != null)
					nextStack.push(node.left);
				if(node.right != null)
					nextStack.push(node.right);
			}
			if(currentStack.isEmpty())
			{
				leftToRight = !leftToRight;
				Stack<BTNode> temp;
				temp = currentStack;
				currentStack = nextStack;
				nextStack = temp;
			}
		}
	}

In a normal level order traversal you call the recursive function traverse() from inside a for loop in some other function, say, calltraversal() - which runs h times (height of the tree).

So in the spiral (zig-zag) manner traversal you have to just flip the pattern of traversing every time you are calling the function from the for loop. It can be done by providing a bool value in the argument, the value is 0 in one call, and then 1 in the next.

void printLevelOrder(struct node* root)
{
  int h = height(root);
  int i; 
  bool value = 0;
  for(i=1; i<=h; i++)
  {
    printGivenLevel(root, i, value );    
    value = ~value ;
  }
}    
 
void printGivenLevel(struct node* root, int level, int value )
{
  if(root == NULL)
    return;
  if(level == 1)
    printf("%d ", root->data);
  else if (level > 1)
  {
    if(value)
    {
      printGivenLevel(root->left, level-1, value );
      printGivenLevel(root->right, level-1, value );
    }
    else
    {
      printGivenLevel(root->right, level-1, value );
      printGivenLevel(root->left, level-1, value );
    }
  }
}

use a queue and a stack..

1. push the root in queue in order of left and right with level information..
2. while dqueue check if level is even, inqueue the child with lvl+1 in queue and print the element.
3. if level is odd inqueue the child and push the element in the stack untill the lvl changes..
4. pop until the stack is empty and print the element.

two stacks

struct Node{
int value;
int visited = 1;
Node * left;
Node * right;
}

void print ZigZag(Node * root) {
printf("%d \n", node->value);
node->visited = 1;
print_in_zig_zag(root);
}

void print_in_zig_zag(Node * node) {
if(node == NULL) return;

if(node->visited == 0) {
node->visited = 1;
printf("%d \n", node->value);
}
else {
print_in_zig_zag(node->left);
print_in_zig_zag(node->right);
}
}

push( stack0, root );
currentstack = stack0;
otherstack = stack1;
level = 0;

while( !currentstack.empty() )
{
	temp = pop(currentstack);
	visit(temp);
	if( level%2 == 0 )
	{
		push( otherstack, temp->right ); // assume push doesn't work if data is NULL
		push( otherstack, temp->left );
	}
	else
	{
		push( otherstack, temp->left );
		push( otherstack, temp->right );
	}
	if( currentstack.empty() )
	{
		swap( currentstack, otherstack ); // pointer swap
		level++;
	}
}

public class Traversal<T> {
	public void ZigZagTraversal(T node){
		Stack<T> current = new Stack<T>();
		Stack<T> next = new Stack<T>();
		BSTNode tmp;
		current.push(node);
		int counter = 0;
		while (!current.isEmpty() | !next.isEmpty()) {
			if (counter % 2 == 0) {
				while (!current.isEmpty()) {
					tmp = (BSTNode) current.pop();
					System.out.println("IF" + tmp.getData());
					if (tmp.getLeft() != null)
						next.push((T) tmp.getLeft());
					if (tmp.getRight() != null)
						next.push((T) tmp.getRight());
				}
			} else {
				while (!next.isEmpty()) {
					tmp = (BSTNode) next.pop();
					System.out.println("Else " + tmp.getData());
					if (tmp.getRight() != null)
						current.push((T) tmp.getRight());
					if (tmp.getLeft() != null)
						current.push((T) tmp.getLeft());
				}
			}
			counter++;
		}
	}
}

a doubly linked list with 4 pointers (2 front, 2 rear, two fixed, 2 movable) and a temporary linked list can solve the problem

{how about using a queue  q and stack s

solution :- 

add root to q
while (!q.isempty() || !s.isempty()){
while (!q.isempty()){
   a= q.pop();
print a;
s.push(a->left);  //adding to stack
s.push(a->right);
}
while (!s.empty()){
a= s.pop();
print a ;
q.push(a->left);
q.push(a->right);
}
}

guys this my first post so not sure about many things please comment is u find any thing wrong with the soln

I'm using BFS. But instead of a queue, at alternative levels I use queue(to print from left to right) and stack(from right to left)

void zigzag(Node * root){
   Queue left_queue; //left to right printing
   Stack right_stack; //  R to L printing
   right_stack.push(root);
   Node * cur;
   while(!left_queue.empty() || right_stack.empty()){
      while(!left_queue.empty()){
            cur = left_queue.pop();
            print cur->data;
            // check for null before putting. should not put if child is null
            right_stack.push(cur->right); 
            right_stack.push(cur->left);
      }
      while(!right_stack.empty()){
           // similar as above, here u read from stack and put it into queue
      }
   }

}