Special DataStructure to Perform Level Order Insertion in a Binary Tree

Write a Function to insert elements in a binary tree following:
1. Insert as Root, If Tree is NULL
2. Insert Left node & Then Right Node in Each Level
3. Once, level is full of nodes, proceed to next level.



Implementation:

#include<stdio.h>
#include<malloc.h>
/*Create a Structure with data, count of the nodes in left subtree(lc), count of the nodes in the right subtree(rc), structure pointer to the left child & right child */
struct node
{
     int data;
     int lc;
     int rc;
     struct node *left , *right;
};
/* Function to create a memory block & store the received data in it & return the address of the newly created memory block */
struct node* newnode ( int data )
{
     struct node *new = ( struct node* ) malloc ( sizeof ( struct node ) );
     new -> data = data;
     new -> left = new -> right = NULL;
     new -> lc = 0; //Since, left subtree is NULL
     new -> rc = 0; //Since, right subtree is NULL
     return new;
}
/* Function insert to find a position to where the new data has to be inserted. */
struct node* insert ( struct node *root , int data )
{
     /* If the tree is empty, insert the new node &    make it as root */
      if ( root == NULL )
          root = newnode ( data );
     else
     {
           /* If the number of nodes in left subtree equals number of nodes in the right subtree, insert the data in the leftmost leaf node */
 
           if ( root -> lc == root -> rc )
           {
                  root -> lc ++; //Update the left count
                  root -> left = insert ( root -> left , data );
           }

           /* If the number of nodes in the left subtree is less than the number of nodes in the right subtree, insert the data in the leftmost leaf node */

           else if ( root -> lc < root -> rc )
           {
                 root -> lc ++; //Update the left count
                 root -> left = insert ( root -> left , data );
           }

           /* If the number of nodes in the right subtree is less than the number of nodes in the left subtree, insert the data in the rightmost leaf node */

           else
           {
                 root -> rc ++; //Update the right count
                 root -> right = insert ( root -> right , data );
           }
     }

     /* Return the original root which is not changed. */
     return root;
}

/* Inorder Function to perform Inorder Traversal.
a. Visit the Left Node
b. Visit the Root Node
c. Visit the Right Node */
void inorder ( struct node *root )
{
     if ( root == NULL )
          return;
     inorder ( root -> left ); //Recur for left subtree
     printf ( "%d   " , root -> data ); //Print the data
     inorder ( root -> right ); //Recur for right subtree
}
int main()
{
     /* Declare the root node & Initialize it as "NULL" */
     struct node *root = NULL; 
     
     int i , data , N;
     /* Create the Root node & insert the data "1" */
     root = insert ( root , 1 ); 
     printf ( "Enter the number of nodes excluding root node:" ) ;
     /* Number of nodes - 1 (root node) */
     scanf ( "%d" , &N ); 
     for ( i = 0 ; i < N ; i ++ )
     {
          printf ( "Enter data[%d]:" , i );
          scanf ( "%d" , &data );
          insert ( root , data );
     }

     /* To print the in-order traversal of the tree */
     inorder ( root );
     return 0;
}

Output:

Enter the number of nodes excluding root node:14
Enter data[0]:2
Enter data[1]:3
Enter data[2]:4
Enter data[3]:5
Enter data[4]:6
Enter data[5]:7
Enter data[6]:8
Enter data[7]:9
Enter data[8]:10
Enter data[9]:11
Enter data[10]:12
Enter data[11]:13
Enter data[12]:14
Enter data[13]:15
8   4   12   2   10   6   14   1   9   5   13   3   11   7   15