Q:

Program to find maximum width of a binary tree

belongs to collection: Tree Programs

robaa
Save to bookmark
|
2022-11-09
|
  174 
0

Explanation

In this program, we need to find out the maximum width of the binary tree. The width of the binary tree is the number of nodes present in any level. So, the level which has the maximum number of nodes will be the maximum width of the binary tree. To solve this problem, traverse the tree level-wise and count the nodes in each level.

In the given binary tree,

Level 1 has one node, so maxWidth = 1.
Level 2 has two nodes, so maxWidth = 2 as (2 > 1).
Level 3 has four nodes, so maxWidth = 4 as (4 > 2).
Level 4 has one node, so maxWidth = 4 as (1 < 4).

So, the maximum width of the above binary tree is 4 denoted by white ellipse.

Algorithm

  1. Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
  3. Define another class which has an attribute root.
    1. Root represents the root node of the tree and initializes it to null.
  4. findMaximumWidth() will find out the maximum width of the given binary tree:
    1. Variable maxWidth will store the maximum number of nodes present in any level.
    2. The queue is used for traversing binary tree level-wise.
    3. It checks whether the root is null, which means the tree is empty.
    4. If not, add the root node to queue. Variable nodesInLevel keeps track of the number of nodes in each level.
    5. If nodesInLevel > 0, remove the node from the front of the queue and add its left and right child to the queue. For the first iteration, node 1 will be removed and its children nodes 2 and 3 will be added to the queue. In the second iteration, node 2 will be removed, its children 4 and 5 will be added to the queue and so on.
    6. MaxWidth will store max(maxWidth, nodesInLevel). So, at any given point of time, it will represent the maximum number of nodes.
    7. This will continue till all the levels of the tree is traversed.

Input:

Output:

Maximum width of the binary tree: 4
Python programming, Php programming, Java programming, C programming, c# programming, examples, Python programming examples, Php programming examples, Java programming examples, C programming examples, c# programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-09
need an explanation for this answer? contact us directly to get an explanation for this answer

Python

#Represent a node of binary tree  
class Node:  
    def __init__(self,data):  
        #Assign data to the new node, set left and right children to None  
        self.data = data;  
        self.left = None;  
        self.right = None;  
   
class BinaryTree:  
    def __init__(self):  
        #Represent the root of binary tree  
        self.root = None;  
      
    #findMaximumWidth() will find out the maximum width of the given binary tree  
    def findMaximumWidth(self):  
        maxWidth = 0;  
        #Variable nodesInLevel keep tracks of number of nodes in each level  
        nodesInLevel = 0;  
        #queue will be used to keep track of nodes of tree level-wise  
        queue = [];  
          
        #Check if root is null, then width will be 0  
        if(self.root == None):  
            print("Tree is empty");  
            return 0;  
        else:  
            #Add root node to queue as it represents the first level  
            queue.append(self.root);  
              
            while(len(queue) != 0):  
                  
                #Variable nodesInLevel will hold the size of queue i.e. number of elements in queue  
                nodesInLevel = len(queue);  
                #maxWidth will hold maximum width.   
                #If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel  
                maxWidth = max(maxWidth, nodesInLevel);  
                  
                #If variable nodesInLevel contains more than one node   
                #then, for each node, we'll add left and right child of the node to the queue  
                while(nodesInLevel > 0):  
                    current = queue.pop(0);  
                    if(current.left != None):  
                        queue.append(current.left);  
                    if(current.right != None):  
                        queue.append(current.right);  
                    nodesInLevel = nodesInLevel - 1;  
        return maxWidth;  
   
bt = BinaryTree();  
#Add nodes to the binary tree  
bt.root = Node(1);  
bt.root.left = Node(2);  
bt.root.right = Node(3);  
bt.root.left.left = Node(4);  
bt.root.left.right = Node(5);  
bt.root.right.left = Node(6);  
bt.root.right.right = Node(7);  
bt.root.left.left.left = Node(8);  
   
#Display the maximum width of given tree  
print("Maximum width of the binary tree: " + str(bt.findMaximumWidth()));

 

Output:

Maximum width of the binary tree: 4

 

C

#include <stdio.h>  
#include <stdlib.h>  
   
//Represent a node of binary tree  
struct node{  
    int data;  
    struct node *left;  
    struct node *right;  
};  
   
//Represent the root of binary tree  
struct node *root = NULL;  
   
//createNode() will create a new node  
struct node* createNode(int data){  
    //Create a new node  
    struct node *newNode = (struct node*)malloc(sizeof(struct node));  
    //Assign data to newNode, set left and right children to NULL  
    newNode->data = data;  
    newNode->left = NULL;  
    newNode->right = NULL;  
      
    return newNode;  
}  
   
//queue will be used to keep track of nodes of tree level-wise  
struct node* queue[100];  
int rear = 0,front = -1, size = 0;  
   
//Adds new node to the queue  
void enqueue(struct node* temp)  
{  
    queue[rear++]=temp;  
    size++;  
}  
//Deletes a node from the queue  
struct node* dequeue()  
{  
    size--;  
    return queue[++front];  
}  
   
//findMaximumWidth() will find out the maximum width of the given binary tree  
int findMaximumWidth() {  
    int maxWidth = 0;  
      
    //Variable nodesInLevel keep tracks of number of nodes in each level  
    int nodesInLevel = 0;  
      
    //Check if root is null, then width will be 0  
    if(root == NULL) {  
        printf("Tree is empty\n");  
        return 0;  
    }  
    else {  
        //Add root node to queue as it represents the first level  
        enqueue(root);  
          
        while(size != 0) {  
            //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue  
            nodesInLevel = size;  
              
            //maxWidth will hold maximum width.   
            //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel  
            maxWidth = (maxWidth < nodesInLevel) ? nodesInLevel : maxWidth;  
   
            //If variable nodesInLevel contains more than one node   
            //then, for each node, we'll add left and right child of the node to the queue  
            while(nodesInLevel > 0) {  
                      
                struct node *current = dequeue();  
                if(current->left != NULL){  
                    enqueue(current->left);      
                }  
                  
                if(current->right != NULL) {  
                    enqueue(current->right);      
                }  
                nodesInLevel--;  
            }  
        }  
    return maxWidth;  
    }  
}  
   
int main()  
{  
    //Add nodes to the binary tree  
    root = createNode(1);  
    root->left = createNode(2);  
    root->right = createNode(3);  
    root->left->left = createNode(4);  
    root->left->right = createNode(5);  
    root->right->left = createNode(6);  
    root->right->right = createNode(7);  
    root->left->left->left = createNode(8);  
      
    //Display the maximum width of the given tree  
    printf("Maximum width of the binary tree: %d", findMaximumWidth());  
    return 0;  
}

 

Output:

Maximum width of the binary tree: 4

 

JAVA

import java.util.LinkedList;  
import java.util.Queue;  
   
public class BinaryTree {  
      
      //Represent the node of binary tree  
      public static class Node{  
        int data;  
        Node left;  
        Node right;  
          
        public Node(int data){  
          //Assign data to the new node, set left and right children to null  
          this.data = data;  
          this.left = null;  
          this.right = null;  
        }  
      }  
        
      //Represent the root of binary tree  
      public Node root;  
        
      public BinaryTree(){  
        root = null;  
      }  
        
      //findMaximumWidth() will find out the maximum width of the given binary tree  
      public int findMaximumWidth() {  
          int maxWidth = 0;  
            
          //Variable nodesInLevel keep tracks of number of nodes in each level  
          int nodesInLevel = 0;  
          //queue will be used to keep track of nodes of tree level-wise  
          Queue<Node> queue = new LinkedList<Node>();  
            
          //Check if root is null, then width will be 0  
          if(root == null) {  
              System.out.println("Tree is empty");  
              return 0;  
          }  
          else {  
              //Add root node to queue as it represents the first level  
              queue.add(root);  
                
              while(queue.size() != 0) {  
                    
                  //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue  
                  nodesInLevel = queue.size();  
                  //maxWidth will hold maximum width.   
                  //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel  
                  maxWidth = Math.max(maxWidth, nodesInLevel);  
                    
                  //If variable nodesInLevel contains more than one node   
                  //then, for each node, we'll add left and right child of the node to the queue  
                  while(nodesInLevel > 0) {  
                     Node current = queue.remove();  
                     if(current.left != null)   
                         queue.add(current.left);  
                     if(current.right != null)   
                         queue.add(current.right);  
                     nodesInLevel--;  
                  }  
              }  
          }  
          return maxWidth;  
      }  
        
      public static void main(String[] args) {  
            
          BinaryTree bt = new BinaryTree();  
          //Add nodes to the binary tree  
          bt.root = new Node(1);  
          bt.root.left = new Node(2);  
          bt.root.right = new Node(3);  
          bt.root.left.left = new Node(4);  
          bt.root.left.right = new Node(5);  
          bt.root.right.left = new Node(6);  
          bt.root.right.right = new Node(7);  
          bt.root.left.left.left = new Node(8);  
            
          //Display the maximum width of given tree  
          System.out.println("Maximum width of the binary tree: " + bt.findMaximumWidth());  
      }  
}

 

Output:

Maximum width of the binary tree: 4

 

C#

using System;  
using System.Collections.Generic;  
namespace Tree   
{                       
    public class Program  
    {  
        //Represent a node of binary tree  
        public class Node<T>{  
            public T data;  
            public Node<T> left;  
            public Node<T> right;  
              
            public Node(T data) {  
                //Assign data to the new node, set left and right children to null  
                this.data = data;  
                this.left = null;  
                this.right = null;  
            }  
        }  
          
        public class BinaryTree<T> where T : IComparable<T>{  
            //Represent the root of binary tree  
            public Node<T> root;  
   
            public static Boolean flag = false;  
   
            public BinaryTree(){  
                root = null;  
            }  
          
        //findMaximumWidth() will find out the maximum width of the given binary tree  
          public int findMaximumWidth() {  
            int maxWidth = 0;  
              
            //Variable nodesInLevel keep tracks of number of nodes in each level  
            int nodesInLevel = 0;  
            //queue will be used to keep track of nodes of tree level-wise  
            Queue<Node<T>> queue = new Queue<Node<T>>();  
              
            //Check if root is null, then width will be 0  
            if(root == null) {  
              Console.WriteLine("Tree is empty");  
              return 0;  
            }  
            else {  
              //Add root node to queue as it represents the first level  
              queue.Enqueue(root);  
                
              while(queue.Count != 0) {  
                    
                  //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue  
                  nodesInLevel = queue.Count;  
                  //maxWidth will hold maximum width.   
                  //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel  
                  maxWidth = (maxWidth < nodesInLevel) ? nodesInLevel : maxWidth;  
                    
                  //If variable nodesInLevel contains more than one node   
                  //then, for each node, we'll add left and right child of the node to the queue  
                  while(nodesInLevel > 0) {  
                     Node<T> current = queue.Dequeue();  
                     if(current.left != null)   
                         queue.Enqueue(current.left);  
                     if(current.right != null)   
                         queue.Enqueue(current.right);  
                     nodesInLevel = nodesInLevel - 1;  
                  }  
              }  
            }  
            return maxWidth;  
      }  
        }  
          
        public static void Main()  
        {  
            BinaryTree<int> bt = new BinaryTree<int>();  
            //Add nodes to the binary tree  
              bt.root = new Node<int>(1);  
              bt.root.left = new Node<int>(2);  
              bt.root.right = new Node<int>(3);  
              bt.root.left.left = new Node<int>(4);  
              bt.root.left.right = new Node<int>(5);  
              bt.root.right.left = new Node<int>(6);  
              bt.root.right.right = new Node<int>(7);  
              bt.root.left.left.left = new Node<int>(8);  
            
              //Display the maximum width of given tree  
              Console.WriteLine("Maximum width of the binary tree: " + bt.findMaximumWidth());                  
        }      
    }  
}

 

Output:

Maximum width of the binary tree: 4

 

PHP

<!DOCTYPE html>  
<html>  
<body>  
<?php  
//Represent a node of binary tree  
class Node{  
    public $data;  
    public $left;  
    public $right;  
      
    function __construct($data){  
        //Assign data to the new node, set left and right children to NULL  
        $this->data = $data;  
        $this->left = NULL;  
        $this->right = NULL;  
    }  
}  
class BinaryTree{  
    //Represent the root of binary tree  
    public $root;  
    function __construct(){  
        $this->root = NULL;  
    }  
      
    //findMaximumWidth() will find out the maximum width of the given binary tree  
    function findMaximumWidth() {  
      $maxWidth = 0;  
        
      //Variable $nodesInLevel keep tracks of number of nodes in each level  
      $nodesInLevel = 0;  
      //$queue will be used to keep track of nodes of tree level-wise  
      $queue = array();  
        
      //Check if root is null, then width will be 0  
      if($this->root == null) {  
          print "Tree is empty <br>";  
          return 0;  
      }  
      else {  
          //Add root node to $queue as it represents the first level  
          array_push($queue,$this->root);  
            
          while(sizeof($queue) != 0) {  
                
              //Variable $nodesInLevel will hold the size of queue i.e. number of elements in queue  
              $nodesInLevel = sizeof($queue);  
              //$maxWidth will hold maximum width.   
              //If $nodesInLevel is greater than $maxWidth then, $maxWidth will hold the value of $nodesInLevel  
              $maxWidth = max($maxWidth, $nodesInLevel);  
                
              //If variable $nodesInLevel contains more than one node   
              //then, for each node, we'll add left and right child of the node to the $queue  
              while($nodesInLevel > 0) {  
                 $current = array_shift($queue);  
                 if($current->left != NULL)   
                     array_push($queue, $current->left);  
                 if($current->right != NULL)   
                     array_push($queue,$current->right);  
                 $nodesInLevel--;  
              }  
          }  
      }  
      return $maxWidth;  
    }  
}  
$bt = new BinaryTree();  
//Add nodes to the binary tree  
$bt->root = new Node(1);  
$bt->root->left = new Node(2);  
$bt->root->right = new Node(3);  
$bt->root->left->left = new Node(4);  
$bt->root->left->right = new Node(5);  
$bt->root->right->left = new Node(6);  
$bt->root->right->right = new Node(7);  
$bt->root->left->left->left = new Node(8);  
            
//Display the maximum width of given tree  
print "Maximum width of the binary tree: " . $bt->findMaximumWidth();  
?>  
</body>  
</html>

 

Output:

Maximum width of the binary tree: 4

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Tree Programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Program to find the largest element in a Binary Tr... >>
<< Program to determine whether two trees are identic...