Maximum Width of Binary Tree

by · January 21, 2021

“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
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:

  1. Introduction to Tree Data Structure
  2. Binary Tree Traversals
  3. Print All Leaf Nodes of a Binary Tree
  4. Count Number of Nodes in a Binary Tree
  5. Print Alternate Levels of Binary Tree
  6. Level Order Tree Traversal
  7. Left View of Binary Tree
  8. Right View of Binary Tree
  9. Compute Height of Binary Tree
  10. Inorder Tree Traversal Using Stack
  11. Preorder Tree Trasversal Using Stack
  12. Postorder Tree Traversal Using Stack
  13. Vertical Order Tree Traversal
  14. Top View of Binary Tree
  15. Bottom View of Binary Tree
  16. Delete Complete Binary Tree
  17. Check if two trees are mirror Trees of Each Other
  18. Convert Binary Tree to its Mirror Tree
  19. Check if Binary Tree is Symmetric or Not
  20. Print All Root to Leaf Paths in a Binary Tree

You may also like...