Maximum Width of a Binary Tree

The maximum width of a binary tree can be defined as the maximum number of the nodes of the binary tree that are present in a particular level of the binary tree. To calculate the maximum width of a binary tree, we need to traverse the tree level and find the maximum number of nodes present at a particular level.

Let’s see an example to understand better the concept of a binary tree’s maximum width in a better way.

In the binary tree displayed above, the root node has value 42 and has its left subtree and right subtree. In this example, let’s calculate the number of nodes present in each binary tree level. The binary tree displayed above has levels starting from level 0 to level 4 (with five levels).

Only a root node is present in level 0 of the shown binary tree, so the number of nodes in level 0 is 1.
In level 1 of the binary tree, there are two child nodes (right child and left child) of the root node having values 29 and 89, respectively, so level 1 of the binary tree has two nodes.
There are three nodes in level 2 of the binary tree (two child nodes of the left subtree root and one right child node of the right subtree root), so there are three nodes in level 2 of the binary tree.
In level 3 of the binary tree, we have two nodes that are child nodes with a value of 99.
In the last level, i.e. level 4 of the binary tree, two nodes are present.

So, the numbers of nodes in each level are:

Level 0: 1 Node

Level 1: 2 Nodes

Level 2: 3 Nodes

Level 3: 2 Nodes

Level 4: 2 Nodes.

So, level 2 has the maximum number of nodes that are 3, three nodes having values 1, 35 and 99, respectively. As level 2 has 3 nodes, the maximum width of a binary tree displayed above in the image is three.

It is not compulsory that all the time, the deepest level should have the maximum number of nodes of the tree, three, and the maximum width of a binary tree is found there. Like in the binary tree shown above, level 2, which is not the deepest level of the binary tree, having the maximum number of nodes (3 nodes).

C++ Code

Let’s write a C++ code better to understand the maximum width of a binary tree.

  // A queue-based C++ program to create a binary tree and find the maximum width   // of the created Binary Tree     // stdc++ header file is included to use object of ostream and istream named cout and cin respectively to display and print data on the console  #include   using namespace std ;       /* A binary tree node has data, a pointer to the left child      and a pointer to right child */  struct Node   {         // a variable named data of integer type is created that will hold the data that is present in that particular node of the complete binary tree      int data ;             // two variables named right and left of the node type are created that will be used to hold the addresses of the right child node and the left child node of a parent node present on the complete binary tree      struct Node * left ;       struct Node * right ;   };//end of the struct Node           // A Function named maxWidth is written to find the maximum width of the binary tree using level order traversal   // And for the level order traversal of the binary tree, the data structure that is used is a queue    // The maxWidth() Function will traverse through the binary tree in level order and will keep on adding each node of the binary tree that is traversed into an object of the queue data structure  // The process of adding elements in the queue data structure is repeated until the maximum width of the binary tree is found   // There is one parameter to the maxWidth() function of struct Node type named root that will represent the root node of the binary tree whose maximum width we need to find   // The return type of the maxWidth() function is of Integer type that will represent the maximum width of the binary tree  int maxWidth(struct Node * root)   {       // First if root is NULL (that means there are no child nodes of the root node) is checked if true then zero value is returned      if (root == NULL)           return 0;           // The result variable of the int type is initialised with zero      int result = 0;           // The level order traversal of the binary tree begins, and the count of the number of nodes in each level of the tree is kept      // and in the last, the maximum number of nodes in a particular level will represent the maximum width of the binary tree              // An object of the queue data structure named q is created to store the nodes of the binary tree      queue q;       q.push(root);       while (!q.empty())       {           // Get the size of queue when the level order           // traversal for one level finishes           int count = q.size() ;               // Update the maximum node count value           result = max(count, result);               // Iterate for all the nodes in the queue currently           while (count–)           {               // Dequeue an node from queue               Node *temp = q.front();               q.pop();                   // Enqueue left and right children of               // dequeued node               if (temp->left != NULL)                   q.push(temp->left);               if (temp->right != NULL)                   q.push(temp->right);           }       }         // in the end, the result variable is returned as the maximum width of the binary tree        return result;   }       /* A function named newNode that allocates a new node with the given data and NULL left and right pointers. */  // There is one parameter to the newNode function of integer type that will represent the data that a particular node is storing in it  struct Node * newNode(int data)   {       struct Node * node = new Node;       node->data = data;       node->left = node->right = NULL;       return (node);   }       //The main function is written to create a binary tree and find the maximum width of the binary tree  int main()   {      /* Construct the tree shown below in the comments                 10               /                 /                  20       30            /      /              /      /               40      50       60                /                /                 70     80      */           // An object named root of the struct named Node is created that will act as a root node of the tree having value 10       struct Node *root = newNode(10);            // add left and right child nodes to the root node of the tree having values 20 and 30 respectively      root->left = newNode(20);      root->right = newNode(30);        // add left child node to the left node of the root node of the tree having value 40      root->left->left = newNode(40);            // add left and right child nodes to the right node of the root node of the tree having values 50 and 60 respectively      root->right->left = newNode(50);      root->right->right = newNode(60);        // add left and right child nodes to the left node of the right node of the root node of the tree having values 70 and 80 respectively      root->right->left->left = newNode(70);      root->right->left->right = newNode(80);                      // * Once the tree is created and all the nodes of the tree are assigned their values, the maxWidth function is called to calculate the maximum width of the binary tree      // * the root of the tree is passed as a parameter to the inorder function              cout << “The Maximum width of the binary tree  is “;      cout << maxWidth(root);      cout << endl;       return 0;   } // end of main fucntions  *>

Output: Run the above code, and it gives the following output.

The Maximum width of the binary tree is 3.

Java Code

To understand the maximum width of a binary tree, let’s write a Java code.

  // A queue-based Java program to create a binary tree and find the maximum width   // of the created Binary Tree     // The LinkedList class is imported from the util package to use the functionalities of the LinkedList data structure  import java.util.LinkedList;   // The Queue class is imported from the util package to use the functionalities of the Queue data structure  import java.util.Queue;             // A class named BinaryTree is created that has the static class named node that will be used to create a Binary Tree and the max-widththe() function to find the maximum width of the Binary Tree  public class BinaryTree    {       // A static class named node is created that will act as a single node of the binary tree       static class node        {                // a variable named data of integer type is created that will hold the data that is present in that particular node of the binary tree          int data;                     // two variables named right and left of the node type are created that will be used to hold the addresses of the right child node and the left child node of a parent node present on the complete binary tree          node left, right;                 // A constructor of the struct named node is written that will have one parameter of integer type that will set its value to the data variable of the static class          public node(int data)            {               this.data = data;           }       } //end of the static class node                // A Function named maxWidth is written to find the maximum width of the binary tree using level order traversal       // And for the level order traversal of the binary tree, the data structure that is used is a queue        // The maxWidth() Function will traverse through the binary tree in level order and will keep on adding each node of the binary tree that is traversed into an object of the queue data structure      // The process of adding elements in the queue data structure is repeated until the maximum width of the binary tree is found       // There is one parameter to the maxWidth() function of struct node type named root that will represent the root node of the binary tree whose maximum width we need to find       // The return type of the maxWidth() function is of Integer type that will represent the maximum width of the binary tree      static int max-width node root)        {   // First if root is NULL (that means there are no child nodes of the root node) is checked if true then zero value is returned          if (root == null)               return 0;                      // The result variable of the int type is initialised with zero          int result = 0;           // The level order traversal of the binary tree begins, and the count of the number of nodes in each level of the tree is kept          // and in the last, the maximum number of nodes in a particular level will represent the maximum width of the binary tree                      // An object of the queue data structure named q is created to store the nodes of the binary tree          Queue q = new LinkedList<>();           q.add(root);           while (!q.isEmpty())            {               // Get the size of queue when the level order               // traversal for one level finishes               int count = q.size();                               // Update the maximum node count value               result = Math.max(result, count);                               // Iterate for all the nodes in                // the queue currently               while (count– > 0)                {                   // Dequeue an node from queue                   node temp = q.remove();                                   // Enqueue left and right children                    // of dequeued node                   if (temp.left != null)                    {                       q.add(temp.left);                   }                   if (temp.right != null)                    {                       q.add(temp.right);                   }               }           }             // in the end, the result variable is returned as the maximum width of the binary tree            return result;       }               //The main fucntion is written to create a binary tree and find the maximum width of the binary tree      public static void main(String[] args)        {                 /* Construct the tree shown below in the comments                     10                   /                     /                      20       30                /      /                  /      /                   40      50       60                    /                    /                     70     80          */                   // // An object named root of the struct named node is created that will act as a the root node of the tree having value 10           // node root = new node(1);                     // // add left and right child nodes to the root node of the tree having values 20 and 30 respectively          // root.left = new node(2);           // root.right = new node(3);           // root.left.left = new node(4);           // root.left.right = new node(5);           // root.right.right = new node(8);           // root.right.right.left = new node(6);           // root.right.right.right = new node(7);                               // An object named root of the struct named node is created that will act as a root node of the tree having value 10           node root = new node(10);            // add left and right child nodes to the root node of the tree having values 20 and 30 respectively          root.left = new node(20);          root.right = new node(30);            // add left child node to the left node of the root node of the tree having value 40          root.left.left = new node(40);            // add left and right child nodes to the right node of the root node of the tree having values 50 and 60 respectively          root.right.left = new node(50);          root.right.right = new node(60);            // add left and right child nodes to the left node of the right node of the root node of the tree having values 70 and 80 respectively          root.right.left.left = new node(70);          root.right.left.right = new node(80);                 // * Once the tree is created and all the nodes of the tree are assigned their values, the maxWidth function is called to calculate the maximum width of the binary tree          // * the root of the tree is passed as a parameter to the inorder function                    // A integer variable named width is created that will hold the width of the Binary tree returned by the maxwidth() function.          int width = maxwidth(root);            System.out.println(“The Maximum width of the binary tree = ” + width);           System.out.println();      }   } // end of the BinaryTree class  

Output: The output of the above code is:

The Maximum width of the binary tree = 3.

Python Code:

To understand the maximum width of a binary tree, let’s write a python code to find the width of a given binary tree.

  # A queue-based Python program to create a binary tree and find the maximum width   # of the created Binary Tree       # A  class named node is created that will act as a single node of the binary tree   class Node:               #a variable named data of integer type is created that will hold the data that is present in that particular node of the binary tree           #two variables named right and left of the node type are created that will be used to hold the addresses of the right child node and the left child node of a parent node present on the complete binary tree      #A constructor of the struct named node is written that will have one parameter of integer type that will set its value to the data variable of the static class            def __init__(self, data):           self.data = data            self.left = None          self.right = None         # A Function named getMaxWidth is written to find the maximum width of the binary tree using level order traversal   # And for the level order traversal of the binary tree, the data structure that is used is the queue  # The getMaxWidth() Function will traverse through the binary tree in level order and will keep on adding each node of the binary tree that is traversed into an object of the queue data structure  # The process of adding elements in the queue data structure is repeated until the maximum width of the binary tree is found   # There is one parameter to the getMaxWidth() fucntion of struct node type named root that will represent the root node of the binary tree whose maximum width we need to find   # The return type of the getMaxWidth() fucntion is of Integer type that will represent the maximum width of the binary tree  def getMaxWidth(root):       # First, if the root is NULL (that means there are no child nodes of the root node) is checked if true, then zero value is returned       if root is None:           return 0            # Thse level order traversal of the binary tree begins, and the count of the number of nodes in each level of the tree is kept      # and in the last, the maximum number of nodes in a particular level will represent the maximum width of the binary tree        # An object of the queue data structure named q is created to store the nodes of the binary tree      q = []           # The maxWidth variable of the int type is initialized with zero      maxWidth = 0              q.insert(0,root)               while (q != []):           # Get the size of queue when the level order           # traversal for one level finishes           count = len(q)                       # Update the maximum node count value           maxWidth = max(count,maxWidth)                       while count != 0 :               count = count-1              temp = q[-1]                 q.pop() ;               if temp.left is not None:                   q.insert(0,temp.left)                    if temp.right is not None:                   q.insert(0,temp.right)           # in the end, the result variable is returned as the maximum width of the binary tree        return maxWidth       # Driver program to test above function       # The main fucntion is written to create a binary tree and find the maximum width of the binary tree  def main():        ”’Construct the tree shown below in the comments                     10                   /                     /                      20       30                /      /                  /      /                   40      50       60                    /                    /                     70     80            ”’                             # An object named root is created that will act as the root node of the tree having the value of 10       root = Node(10);        # add left and right child nodes to the root node of the tree having values 20 and 30 respectively      root.left = Node(20);      root.right = Node(30);        # add left child node to the left node of the root node of the tree having the value of 40      root.left.left = Node(40);        # add left and right child nodes to the right node of the root node of the tree having values 50 and 60 respectively      root.right.left = Node(50);      root.right.right = Node(60);        # add left and right child nodes to the left node of the right node of the root node of the tree having values 70 and 80 respectively      root.right.left.left = Node(70);      root.right.left.right = Node(80);            # Once the tree is created and all the nodes of the tree are assigned their values, the maxWidth function is called to calculate the maximum width of the binary tree      # the root of the tree is passed as a parameter to the inorder function      width = getMaxWidth(root)      print(“The Maximum width of the binary tree is “, width)       # main function is called  main()  

Output: The output of the above code is:

The Maximum width of the binary tree is 3.

Next TopicTypes of Graph in Data Structure

Maximum Width of a Binary Tree

Maximum Width of a Binary Tree

C++ Code

Java Code

Python Code:

Cycle Sort

Characteristics of OLAP

You may also like