- Write a C program to find the maximum width of a binary tree.
Given a binary tree, we have to find the maximum width of a binary tree. Maximum width of a binary tree is defined as the maximum number of nodes in any of the level of binary tree.
Method 1 : By traversing binary tree multiple times
- Find height of the binary tree, let it be H.
- Traverse the tree using pre order traversal and find number of nodes in one level at a time.
- Check if the number of nodes in current level is more than the maximum width we found till now. If yes then update maximum width of binary tree.
- In this approach, we will traverse given tree H-1 times because in every traversal we are finding node count of one level
C program to find maximum width of a binary tree
#include <stdio.h>
struct node {
int data;
struct node *left;
struct node *right;
};
struct node* getNewNode(int data) {
/* dynamically allocate memory for a new node */
struct node* newNode = (struct node*)malloc(sizeof(struct node));
/* populate data in new Node */
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
/*
This function returns below tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
struct node* generateBTree(){
// Root Node
struct node* root = getNewNode(1);
root->left = getNewNode(2);
root->right = getNewNode(3);
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
root->right->right = getNewNode(7);
root->left->left->left = getNewNode(8);
root->left->left->right = getNewNode(9);
return root;
}
/* Returns maximum of two given numbers */
int getMax(int a, int b){
if(a >= b)
return a;
else
return b;
}
/* Returns height of binary tree */
int getHeight(struct node *root){
int leftHeight, rightHeight;
if(root == NULL)
return 0;
leftHeight = getHeight(root->left);
rightHeight = getHeight(root->right);
return getMax(leftHeight, rightHeight) + 1;
}
/* Calculates the number of nodes in a level,
It populates the address pointed by width
*/
void getLevelWidth(struct node* root, int currentLevel, int level, int *width) {
if(root == NULL) {
return;
}
if(currentLevel == level) {
*width = *width + 1;
return;
}
getLevelWidth(root->left, currentLevel+1, level, width);
getLevelWidth(root->right, currentLevel+1, level, width);
}
/* It returns the maximum width of a binary tree.
It calculates the width of every level and takes maximum of all */
int getMaxWidth(struct node* root) {
int i, width, height, maxWidth = -1;
height = getHeight(root);
for(i = 0; i < height ; i++){
width = 0;
getLevelWidth(root, 0, i, &width);
maxWidth = getMax(width, maxWidth);
}
return maxWidth;
}
int main() {
struct node *root = generateBTree();
printf("Maximum Width of Tree = %d", getMaxWidth(root));
getchar();
return 0;
}
OutputMaximum Width of Tree = 4
Method 2 : By traversing binary tree only once
In method 1, we were traversing binary tree multiple time but in this approach we will traverse only once. We will use an integer array to count the number of nodes in all levels. During pre order traversal, we will keep track of level of current node and increment the counter corresponding to current level.
Time Complexity : O(n), we are traversing binary tree only once.
Time Complexity : O(n), we are traversing binary tree only once.
C program to find maximum width of a binary tree in single traversal
#include <stdio.h>
struct node {
int data;
struct node *left;
struct node *right;
};
struct node* getNewNode(int data) {
/* dynamically allocate memory for a new node */
struct node* newNode = (struct node*)malloc(sizeof(struct node));
/* populate data in new Node */
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
/*
This function returns below tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
struct node* generateBTree(){
// Root Node
struct node* root = getNewNode(1);
// Level 2 nodes
root->left = getNewNode(2);
root->right = getNewNode(3);
// Level 3 nodes
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
root->right->right = getNewNode(7);
// Level 4 nodes
root->left->left->left = getNewNode(8);
root->left->left->right = getNewNode(9);
return root;
}
/* Returns maximum of two given numbers */
int getMax(int a, int b){
if(a >= b)
return a;
else
return b;
}
/* Returns height of binary tree */
int getHeight(struct node *root){
int leftHeight, rightHeight;
if(root == NULL)
return 0;
leftHeight = getHeight(root->left);
rightHeight = getHeight(root->right);
return getMax(leftHeight, rightHeight) + 1;
}
/* It returns the maximum width of a binary tree.
It calculates the width of every level and takes maximum of all */
int getMaxWidth(struct node* root) {
int i, height, maxWidth = -1, counterArray[100] = {0};
height = getHeight(root);
preOrderTraversal(root, counterArray, 0);
for(i = 0; i < height ; i++){
maxWidth = getMax(counterArray[i], maxWidth);
}
return maxWidth;
}
/*
Does preOrder Traversal of a binary tree and
stores the number of nodes in array
*/
void preOrderTraversal(struct node *root, int *array, int level){
if(root != NULL){
/* INcrement the count of nodes in index level */
array[level] = array[level] +1;
/* Recursively pre Order traversal of left sub-tree */
preOrderTraversal(root->left, array, level+1);
/* Recursively pre Order traversal of right sub-tree */
preOrderTraversal(root->right, array, level+1);
}
}
int main() {
struct node *root = generateBTree();
printf("Maximum Width of Tree = %d", getMaxWidth(root));
getchar();
return 0;
}
OutputMaximum Width of Tree = 4