Maximum width of a binary tree

Question: Given a binary tree, write a function to get the maximum width of the given tree. Width of a tree is maximum widths of all levels.

Let us consider the below example tree.

        1
        /  \
       2    3
     /  \     \
    4    5     8
              /  \
             6    7

For the above tree,

width of level 1 is 1,

width of level 2 is 2,

width of level 3 is 3

width of level 4 is 2.

So the maximum width of the tree is 3.

Solution:

Method 1 (Using Level Order Traversal)

This method mainly involves two functions. One is to count nodes at a given level (getWidth), and other is to get the maximum width of the tree(getMaxWidth). getMaxWidth() makes use of getWidth() to get the width of all levels starting from root.

/*Function to print level order traversal of tree*/
getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
  width =   getWidth(tree, i);
  if(width > maxWdth)
      maxWdth  = width
return width

/*Function to get width of a given level */
getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1; 
else if level greater than 1, then
    return getWidth(tree->left, level-1) +
    getWidth(tree->right, level-1);

-----------------
Code in Java:
-----------------
   public int height(TreeNode T) {
        if(T==null)
            return 0;
        return Math.max(height(T.left),height(T.right))+1;
    }
    
    public int getMaxWidth(TreeNode root) {
        int maxWidth=0;
        int height = height(root);
        for(int i=1; i<=height; i++) {
            int width=getWidth(root, i);
            if(width>maxWidth) {
                maxWidth=width;
            }
        }
        return maxWidth;
    }
    
    public int getWidth(TreeNode T, int level) {
        if(T==null) 
            return 0;
        if(level==1)
            return 1;
        else 
            return getWidth(T.left, level-1)+getWidth(T.right, level-1);

    }

Method 2 (Using Preorder Traversal)

In this method we create a temporary array count[] of size equal to the height of tree. We initialize all values in count as 0. We traverse the tree using preorder traversal and fill the entries in count so that the count array contains count of nodes at each level in Binary Tree.

/* Function to get the maximum width of a binary tree*/

int getMaxWidth(struct node* root)

{

  int width;

  int h = height(root);

  // Create an array that will store count of nodes at each level

  int *count = (int *)calloc(sizeof(int), h);

  int level = 0;

  // Fill the count array using preorder traversal

  getMaxWidthRecur(root, count, level);

  // Return the maximum value from count array

  return getMax(count, h);

}

// A function that fills count array with count of nodes at every

// level of given binary tree

void getMaxWidthRecur(struct node *root, int count[], int level)

{

  if(root)

  {

    count[level]++;

    getMaxWidthRecur(root->left, count, level+1);

    getMaxWidthRecur(root->right, count, level+1);

  }

}