# Maximum Width of Binary Tree

Maximum Width of Binary Tree” is a basic problem of Tree data structure. Here, we are given a binary tree and our task is to find maximum width of Binary Tree.

Maximum Width of Binary Tree is defined as maximum number of nodes present at any level of Binary Tree.

Here, we will modify the Level Order Traversal with queue data structure to find maximum width of Binary Tree.

The steps required to find maximum width of Binary Tree are as follows:

1. Create a queue and push root node into it.
2. Initialize maxWidth = 0.
3. Perform following until queue is not empty:
1. CurrSize = queue.size()
2. Assign maxWidth = max(CurrSize, maxWidth)
3. Loop(i=1 to CurrSize)
1. currNode = queue.front()
2. If left or right node exist, push into queue.
3. Queue.pop()

#### C++ Program to Maximum Width of Binary Tree is as follows:

```/* C++ Program to Find Maximum Width of Binary Tree*/
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;

/* Function to compute maximum width of Binary Tree */
void maxWidth(Node *root)
{
/* Checking Base Case */
if(root == NULL)
return;

/* Create Queue and root node */
queue<Node *> que;
que.push(root);

/* Initialize temp variable indicating max width of Binary Tree */
int maxWidth = 0;

while(!que.empty())
{
int currSize = que.size();

maxWidth = max(maxWidth,currSize);

for(int i = 1; i <= currSize; i++)
{
Node *temp = que.front();

que.pop();

if(temp -> left)
que.push(temp -> left);

if(temp -> right)
que.push(temp -> right);
}
}

cout<<maxWidth;
}

int main()
{
/* Creating a Binary tree and inserting some nodes in it */
Node *root = NULL;

root = new Node(1);
root -> left = new Node(2);
root -> right = new Node(3);
root -> left -> left = new Node(4);
root -> left -> right = new Node(5);
root -> right -> left = new Node(6);
root -> right -> right = new Node (7);
root -> left -> right -> left = new Node(8);
root -> right -> left -> right = new Node(9);

/* Calling function to Compute maximum width of Binary Tree*/
cout<<"The Maximum Width of the Given Binary Tree is: ";
maxWidth(root);
}

```

OUTPUT:

`The Maximum Width of the Given Binary Tree is: 4`

Related Posts: