#include<stdio.h>
#include<stdlib.h>
struct node
{
    struct node *left;
	struct node *right;
	int info;
};
struct node *create(struct node *root,int n)
{
	if(root==NULL)
	{
		root=(struct node *)malloc(sizeof(struct node));
		root->info=n;
		root->left=NULL;
		root->right=NULL;
		return root;
	}
	else if(n<root->info)
	{
		root->left=create(root->left,n);
	}
	else if(n>root->info)
	{
		root->right=create(root->right,n);
	}
	else
	printf("\nDUPLICATE ELEMENTS NOT ALLOWED:\n");
	return root;
}
int height(struct node *root)
{
	if(root==NULL)
	return 0;
	int left=height(root->left);
	int right=height(root->right);
	if(left>right)
	return left+1;
	else
	return right+1;
}
void getlevel(struct node *root,int n,int p)
{
	if(root==NULL)
	return;
	if(n==0)
	{
		printf("%d ",root->info);
		return;
	}
	if(n>0)
	{
		if(p==1)
	    {
		 getlevel(root->left,n-1,p);
		 getlevel(root->right,n-1,p);
	    }
	    if(p==-1)
	    {
		 getlevel(root->right,n-1,p);
		 getlevel(root->left,n-1,p);
	    }
	}
}
void levelorder(struct node *root)
{
	int i;
	int p=1;
	int h=height(root);
    for(i=0;i<h;i++)
    {
    	p=(p)*(-1);
    	getlevel(root,i,p);
    }	
}
int main()
{
	struct node *root=NULL;
	int n,p,i;
	printf("Enter the number of nodes in the tree:\n");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Enter value of Node:\n");
		scanf("%d",&p);
		root=create(root,p);
	}
	printf("Root is ->%d\n",root->info);
	levelorder(root);
	return 0;
}