Find maximum width of a Binary Tree.

Solution #1: Maximum width of a tree is explained in the below e.g. 

                 4

             /       \

          5           7

       /     \       /

     9       8    3

Width of level 1: 1

Width of level 2: 2

Width of level 3: 3

Therefore, maximum width: 3

We will first write a function to calculate the width at a given level and then will use this function to determine the maximum width of the tree. Here is the code,

int width(struct node* root, int level)
{
    if(root == NULL)
        return 0;

    if(level == 1)
        return 1;

    return width(root->left, level-1) + width(root->right, level-1);
}

int maxWidth(struct node* root)
{
    if(root == NULL)
        return 0;

    int maxW = 0;
    int curW = 1;
    int level=2;

    while(curW)
    {
        curW = width(root, level++);

        maxW = MAX(curW, maxW);
    }

    return maxW;
}