Spiral traversal of binary tree

Given a binary tree , print it’s nodes in spiral fashion. Example for Given Tree,Output should be F,B,G,I,D,A,C,E,H

This is also called zig zag tree traversal.

Algorithm :
We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level?
If we think logically then we will see that we need stack in place of queue. Now again a single stack won’t serve our purpose here, we need 2 stacks: One stack for printing node from left to right and one stack for printing node from right to left. Note that for printing node from left to right,right node has to be push first into stack. All nodes of one level are put in either one of these stacks.

In the code given below, stack1 has been used for printing nodes from right to left and stack2 has been used for printing nodes from left to right.

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

	stack stack1;
	stack stack2;

	stack1.push(root);

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

		}

		while (stack2.empty() == false)
		{

			struct node *node = stack2.top();
			stack2.pop();
			cout << node->data << " "; 			
			if(node->left)
				stack1.push(node->left);
			if(node->right)
				stack1.push(node->right);
		}
	}
}

Time Complexity : O(n)