Level order traversal in Spiral form

Write a function to print spiral order traversal of a tree or Write function for Tree traversal in Spiral ZigZag form
For below tree, function should print 1, 2, 3, 7, 6, 5, 4.

           [1]
          /   \
       [2]     [3]
      /  \    /   \
    [4]  [5] [6]  [7]

1) Recursive

For odd height , we print tree from Reverse ie,for node (1), (4,5,6,7) , …
For Even height, we print tree from Front (2,3)
to do that in Level Order Traversal, we introduce variable flip and with that we can do that.

Algorithm

printSpiral(tree){
   bool flip = false;
   for H = 1 to height(tree){
      printGivenLevel(root, H, flip);
      flip =!  flip
   }
}
printGivenLevel(root, height, flip){
if root is NULL then return;
if heightis 1, then
    print(root->data);
else if height greater than 1, then
    if(flip)
        printGivenLevel(root->left, height-1, flip);
        printGivenLevel(root->right, height-1, flip);
    else
        printGivenLevel(root->right, height-1, flip);
        printGivenLevel(root->left, height-1, flip);
}

2) Iterative

Keep Two Stack S1, S2.
For Above example
Push 1 to S1.
Push 2,3 (R & L of 1) to S2.
Push 7,6 ( L & R of 3) to S1 and Push 5,4 (L & R of  2) to S1.
Continue this process

Algorithm

 

void printSpiral(struct node *root){
if root is NULL then return
stack<struct node*> S1
stack<struct node*> S2

S1.push(root)

While(S1 & S2 is not Empty){ //till both are not empty

  while(S1 not Empty){

  struct node *temp = S1.top()
  S1.pop()
  print temp->data
  //Push right and then left to S2//
  if(temp->right) S2.push(temp->right)
  if(temp->left) S2.push(temp->left) 

  }//while(s1 !Empty)

  while(S2 not Empty){

  struct node *temp = S2.top()
  S2.pop()
  print temp->data
  //Push left and then right to S1//
  if(temp->left) S1.push(temp->left)
  if(temp->right) S1.push(temp->right) 

  }//while(s2 !Empty)

  
}//While(S1,S2!Empty)

Code with Stack method

// C++ implementation of a O(n) time method for spiral order traversal
#include <iostream>
#include <stack>
using namespace std;

struct node
{
	int data;
	struct node *left, *right;
};
struct node* newNode(int data)
{
	struct node* node = new struct node;
	node->data = data;
	node->left = NULL;
	node->right = NULL;

	return(node);
}

void printSpiral(struct node *root)
{
	if (root == NULL) return;

	stack<struct node*> stack1;
	stack<struct node*> stack2;

	stack1.push(root);

	while (!stack1.empty() || !stack2.empty())
	{
		while (!stack1.empty())
		{
			struct node *temp = stack1.top();
			stack1.pop();
			cout << temp->data << " ";
			if (temp->right)
				stack2.push(temp->right);
			if (temp->left)
				stack2.push(temp->left);
		}
		while (!stack2.empty())
		{
			struct node *temp = stack2.top();
			stack2.pop();
			cout << temp->data << " ";
			if (temp->left)
				stack1.push(temp->left);
			if (temp->right)
				stack1.push(temp->right);
		}
	}
}

int main()
{
	struct node *root = newNode(1);
	root->left	 = newNode(2);
	root->right	 = newNode(3);
	root->left->left = newNode(7);
	root->left->right = newNode(6);
	root->right->left = newNode(5);
	root->right->right = newNode(4);
	cout << "Spiral Order traversal of binary tree is \n";
	printSpiral(root);

	return 0;
}

See working code at http://ideone.com/4VM6us