CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to find maximum width of a binary treeExplanationIn 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 levelwise and count the nodes in each level. In the given binary tree, Level 1 has one node, so maxWidth = 1. So, the maximum width of the above binary tree is 4 denoted by white ellipse. Algorithm
SolutionPython#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 levelwise 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 levelwise 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 JAVAimport 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 levelwise 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 levelwise 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 levelwise $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
Next TopicPrograms List
