Get Maximum width of Binary Tree

Question:

Given a binary tree root node, get the maximum width of that tree

Example:

Consider the image given below

Width at level 1 is 1. Because it has only 1 node.
Width at level 2 is 2. Because it has only 2 nodes.
Width at level 3 is 4. Because it has only 4 nodes.

Solution:

While doing level order traversal, compute the number of nodes at each level.

Then get the max of nodes at each level and display the result.

Solution

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

int get_max_width(Node *root) 
{ 
    if (root == NULL) 
        return 0; 
  
    int result = 0; 
  
    queue<Node*> q; 
    q.push(root); 
    while (!q.empty()) 
    { 
        //get the size of the queue
        int count = q.size() ; 

        result = max(count, result); 
  
        //this loop will get all the nodes at a particular level
        while (count > 0) 
        { 
            Node *temp = q.front(); 
            q.pop(); 
  
            if (temp->left != NULL) 
                q.push(temp->left); 
            if (temp->right != NULL) 
                q.push(temp->right); 

            count --;
        } 
    } 
  
    return result; 
} 

int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    cout<<"The max width of the binary tree is = "<< get_max_width(root)<<endl;

    return 0;  
}  

Output:

The max width of the binary tree is = 4