/* ARRAY IMPLEMENTATION OF BINARY TREE */

/* here a counter is used to keep track of number of nodes */
/* also since left & right exist , hence counter is used during insertion */
/* to connect new insertion to tree */

#include<stdio.h>
#define SIZE 5

struct node
{
 int data,left,right;
};

struct node elements[SIZE];      /*Global Declaration*/


void create()
{
 int i=0;
 for(i=0;i<SIZE;i++)
    {
     elements[i].data=0;
     elements[i].left=-1;
     elements[i].right=-1;
    }
}

void insert(int *avail,int n,int *count)
{
 int i,j;
 if(*avail==-1)
   {
    *avail=0;
    elements[*avail].data=n;
    *count=0;
   }
 else
   {
    i=*avail;
    while(i!=-1)
         {
          j=i;
          if(n<elements[i].data)
            {
             i=elements[i].left;
            }
          else
            {
             i=elements[i].right;
            }
         }
    (*count)++;
    if(n<elements[j].data)
      {
       elements[j].left=*count;
       elements[*count].data=n;
      }
    else
      {
       elements[j].right=*count;
       elements[*count].data=n;
      }
   }
}

void main()
{
 int i=0,ch,n,avail=-1,count=-1;
 create();
 do
  {
   printf("\nenter choice:\n");
   printf("1.insert in binary tree\n2.display\n3.exit\n");
   scanf("%d",&ch);
   switch(ch)
     {


      case 1: if(count!=(SIZE-1))
                {
                 printf("\nenter data:\n");
                 scanf("%d",&n);
                 insert(&avail,n,&count);
                }
              else
                {
                 printf("\nbinary tree is full\n");
                }
              break;

      case 2: if(avail==-1)
                {
                 printf("\nbinary tree is empty\n");
                }
              else
                {
                 for(i=0;i<=count;i++)
                    {
                     printf("\n%d\t%d\t%d\n",elements[i].left,elements[i].data,elements[i].right);
                    }
                }
              break;
     }
  }
 while(ch!=3);
}