Maximum width of a binary tree | GeeksforGeeks

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

Method 1 (Using Level Order Traversal)
We can use Queue based level order traversal to optimize the time complexity of this method. The Queue based level order traversal will take O(n) time in worst case.

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.

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);

  }

}

Read full article from Maximum width of a binary tree | GeeksforGeeks