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