#include<stdio.h>
#include<stdlib.h>

typedef int Data;
typedef struct N Node;

struct N
{
	Data val;
	struct N *left;
	struct N *right;
};

typedef struct Elem queueNode;
typedef struct Q Queue;

struct Elem
{
	Node* val;
	struct Elem* next;
};

struct Q
{
	queueNode *front;
	queueNode *rear;
};

Queue* createQueue()
{
	Queue *q;
	q=(Queue *)malloc(sizeof(Queue));
	if (q==NULL)
		return NULL;
	q->front=q->rear=NULL;
	return q;
}

int isEmpty(Queue*q)
{
	return q->front==NULL;
}

void enQueue(Queue*q,Node* v)
{
	queueNode* newNode=(queueNode*)malloc(sizeof(queueNode));
	newNode->val=v;
	newNode->next=NULL;
	if (q->rear==NULL)
		q->rear=newNode;
	else
		{
			(q->rear)->next=newNode;
			(q->rear)=newNode;
		}
if (q->front==NULL) q->front=q->rear;
}

Node* deQueue(Queue*q)
{
Node* d=NULL;
queueNode* newNode;
if (isEmpty(q))
	return d;
newNode=q->front;
d=newNode->val;
q->front=(q->front)->next;
free(newNode);
return d;
};

void levelOrderTraversalNRec (Node*root)
{
if (root==NULL)
	return;
Queue *Q = createQueue();
enQueue(Q, root);
while (!isEmpty(Q))
{
root=deQueue(Q);
printf ("%d ", root->val);
if (root ->left!=NULL) enQueue(Q,root ->left);
if (root ->right!=NULL) enQueue(Q,root ->right);
}
}