DAA: Algorithm to Find the Maximum Width of a Tree
Algorithm to Find the Maximum Width of a Tree
The width of a binary tree is defined as the maximum number of nodes at a given level. The level having the maximum number of nodes will be the width of the binary tree.
In the given tree,
Level 1 has one node.
Level 2 has two nodes.
Level 3 has three nodes.
Hence the maximum width of the tree is 3.
To do this, we have two methods:
Approach 1
In this approach, we will calculate the height of the tree. Using the height, we will go to each level and count the total number of nodes. Each time the nodes are calculated, they will be updated with the current maximum width.
C++ code:
#include <bits/stdc++.h>
using namespace std;
// Create the tree structure
class Node {
public:
int data; // value of a Node
Node *left, *right; // The left and right pointers to the Node
};
// Function to insert a new node
Node* newnode(int data)
{
Node* root = new Node(); // create root Node
root->data = data; // insert the value
root->left = root->right = NULL; // the left and right child are null currently
return root;
}
// Function to find the height of the tree
int Height(Node* root)
{
// if root is NULL
if (root == NULL)
return 0;
else {
// Calculate height of left subtree
int l_height = Height(root->left);
// Calculate height of the right subtree
int r_height = Height(root->right);
return l_height > r_height ? l_height + 1 : r_height + 1;
}
}
// Function to find nodes at given level
int findWidth(Node* root, int level)
{
if (root == NULL)
return 0;
if (level == 1)
return 1;
// find for left and right
return findWidth(root->left, level - 1) + findWidth(root->right, level - 1);
}
// Function to find the maximum width
int max_width(Node* root)
{
int maxwidth = 0; // Initialise max width as zero
int height = Height(root); // Calculate the Height of the tree
// for each level find the maximum width
for (int i = 1; i <= height; i++) {
int width = findWidth(root, i); // find width at ith level
maxwidth = max(maxwidth, width); // update maxwidth
}
return maxwidth;
}
int main() // Main function
{
Node* root = newnode(1); // declare root node
root->left = newnode(2); // Left child of root
root->right = newnode(3); // Right child of root
root->left->left = newnode(4); // Left child of left parent
root->right->left = newnode(5); // Left child of right parent
root->right->right = newnode(6); // Right child of right parent
cout << "The maximum width of the tree is " << max_width(root);
return 0;
}
C code:
#include <stdlib.h>
#include <stdio.h>
// Create the tree structure
struct Node {
int data; // value of a Node
struct Node *left, *right; // The left and right pointers to the Node
};
// Function to insert a new node
struct Node* newnode(int data)
{
struct Node* root = (struct Node*)(malloc(sizeof(struct Node))); // create root Node
root->data = data; // insert the value
root->left = root->right = NULL; // the left and right child are null currently
return root;
}
// Function to find the height of the tree
int Height(struct Node* root)
{
// if root is NULL
if (root == NULL)
return 0;
else {
// Calculate height of left subtree
int l_height = Height(root->left);
// Calculate height of the right subtree
int r_height = Height(root->right);
return l_height > r_height ? l_height + 1 : r_height + 1;
}
}
// Function to find nodes at given level
int findWidth(struct Node* root, int level)
{
if (root == NULL)
return 0;
if (level == 1)
return 1;
// find for left and right
return findWidth(root->left, level - 1) + findWidth(root->right, level - 1);
}
// Function to find the maximum width
int max_width(struct Node* root)
{
int maxwidth = 0; // Initialise max width as zero
int height = Height(root); // Calculate the Height of the tree
// for each level find the maximum width
for (int i = 1; i <= height; i++) {
int width = findWidth(root, i); // find width at ith level
// update maxwidth
if (width > maxwidth)
maxwidth = width;
}
return maxwidth;
}
int main() // Main function
{
struct Node* root = newnode(1); // declare root node
root->left = newnode(2); // Left child of root
root->right = newnode(3); // Right child of root
root->left->left = newnode(4); // Left child of left parent
root->right->left = newnode(5); // Left child of right parent
root->right->right = newnode(6); // Right child of right parent
printf("The maximum width of the tree is %d", max_width(root));
return 0;
}
Output:
The Maximum Width of the Tree is 3
Approach 2
In this approach, we use a queue data structure to count all the nodes at a particular level. The maximum size of the queue will give the maximum width of the tree. Since it will be a level order traversal, all the existing child nodes will be pushed to the queue after each level is traversed.
C++ code:
#include <bits/stdc++.h>
using namespace std;
// Create the tree structure
class Node {
public:
int data; // value of a Node
Node *left, *right; // The left and right pointers to the Node
};
// Function to insert a new node
Node* newnode(int data)
{
Node* root = new Node(); // create root Node
root->data = data; // insert the value
root->left = root->right = NULL; // the left and right child are null currently
return root;
}
// Function to find the maximum width
int max_width(Node* root)
{
if (root == NULL) // if the tree has 0 nodes
return 0;
int result = 0; // the max_width is set to zero
queue<Node*> q; // Create a queue to to level order traversal
q.push(root); // Push root in the queue
while (!q.empty()) {
int count = q.size(); // Calculate the current maximum width and no of nodes
result = max(count, result); // Update the current maximum with the result
while (count--) { // Iterate until all nodes are traversed
Node* temp = q.front(); // Take the front node
q.pop(); // POP it as we have to find its child nodes
if (temp->left != NULL) // If left child exist enter in queue
q.push(temp->left);
if (temp->right != NULL) // If right child exist enter in queue
q.push(temp->right);
}
}
return result;
}
int main()
{
Node* root = newnode(1); // declare root node
root->left = newnode(2); // Left child of root
root->right = newnode(3); // Right child of root
root->left->left = newnode(4); // Left child of left parent
root->right->left = newnode(5); // Left child of right parent
root->right->right = newnode(6); // Right child of right parent
cout << "The maximum width of the tree is " << max_width(root);
return 0;
}
Output:
The maximum width of the tree is 3
Time Complexity: O(N) where N is the number of nodes
Space. Complexity: O(max_width) i.e., maximum width of the tree