MAXIMUM WIDTH OF BINARY SEARCH TREE

C IMPLEMENTATION:

#include <stdio.h>
#include <stdlib.h>
struct node
{
   int data;
   struct node* left;
   struct node* right;
};
struct node* newNode(int data)
{
    struct node* node=(struct node* )malloc(sizeof(struct node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
   
    return (node);
}
struct node* insert(struct node* node,int data)
{
    if(node==NULL)
       return newNode(data);
    if(data < node->data)
     node->left=insert(node->left,data);
    else
      node->right=insert(node->right,data);

    return(node);
}

int height(struct node* node)
{
   if (node==NULL)
     return 0;
   else
   {
     /* compute the height of each subtree */
     int lHeight = height(node->left);
     int rHeight = height(node->right);
     /* use the larger one */
   
     return (lHeight > rHeight)? (lHeight+1): (rHeight+1);
   }
}
int getWidth(struct node* root, int level)
{
    
  if(root == NULL)
    return 0;
  
  if(level == 1)
    return 1;
            
  else if (level > 1)
    return getWidth(root->left, level-1) +
             getWidth(root->right, level-1);
}
int printwidth(struct node* node)
{
    int max=0;
    int h=height(node);
    int width,i;
    for(i=1;i<=h;i++)
    {
        width=getWidth(node,i);
        if(max < width)
          max=width;
    }

    return max;
}

void inorder(struct node* node)
{
 
    if(node==NULL)
      return;
    inorder(node->left);
    printf("%d ",node->data);
     inorder(node->right);

   
}
int main()
{
    struct node* root=NULL;
    root=insert(root,5);
    insert(root,8);
      insert(root,6);
        insert(root,4);
          insert(root,1);
          insert(root,3);
    printf("\ninorder travesal\n");        
  inorder(root);
   printf("\nmaximum width of binary tree\n");
   printf("%d",printwidth(root));
    return 0;
}

OUTPUT: