Spiral (ZigZag printing) Printing the Binary Tree nodes in C

This is a variant of level order printing. In level order printing we can use iterative or a queue based approach. Iterative option is still available in this one too.But we are trying to follow a non iterative approach here. Instead of a queue we will have two stacks for implementing Sprial printing (also called ZigZag printing) of the Binary Tree. First we push the root node to stack one. Then we visit both stacks and take the top item and store it in a temp variable, then we will pop the stack from which we had pushed the binary tree node. At the same time we will push into the alternate stack the children of the temporary node we had stored. On one stack we will push in right then left child order and in the other one we will be pushing in left and then right children order.

For a binary tree like below

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

 the spiral printing order will be as below:

 1
23
7654

 Below is the implementation:

	#include <stdio.h>
	#include <stdlib.h>
	#include <stack>
	using namespace std;
	typedef struct node {
	int data;
	node *left, *right;
	}node;
	void printSpiralBinary(node * root)
	{
	if (root == NULL) return;
	stack <node *> s1;
	stack <node *> s2;
	s1.push(root);
	while (!s1.empty() || !s2.empty())
	{
	while (!s1.empty())
	{
	node * temp = s1.top();
	s1.pop();
	printf("%d", temp->data);
	if (temp->right) s2.push(temp->right);
	if (temp->left) s2.push(temp->left);
	}
	printf("\n");
	while (!s2.empty())
	{
	node * temp = s2.top();
	s2.pop();
	printf("%d", temp->data);
	if (temp->left) s1.push(temp->left);
	if (temp->right) s1.push(temp->right);
	}
	printf("\n");
	}
	}
	node * newNode(int data)
	{
	node * temp = (node *)malloc(sizeof(node));
	temp->data = data;
	temp->left = temp->right = NULL;
	return temp;
	}
	int main()
	{
	node *root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);
	printf("Sprial level Order traversal of binary tree \n");
	printSpiralBinary(root);
	getchar();
	return 0;
	}

view raw SprialPrintBST.c hosted with ❤ by GitHub