WAP to Calculate The Maximum Width of Binary Tree With & Without Recursion

Given a binary tree, write a function to get the maximum width of the given tree. Width of a tree is maximum of widths of all levels.

Let us consider the below example tree.

1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
For the above tree,
width of level 1 is 1,
width of level 2 is 2,
width of level 3 is 3
width of level 4 is 2.

So the maximum width of the tree is 3.



Algortihm:
There are basically two functions. One is to count nodes at a given level (getWidth), and other is to get the maximum width of the tree(getMaxWidth). getMaxWidth() makes use of getWidth() to get the width of all levels starting from root.

/*Function to print level order traversal of tree*/
getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
width = getWidth(tree, i);
if(width > maxWdth)
maxWdth = width
return width
/*Function to get width of a given level */
getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1;
else if level greater than 1, then
return getWidth(tree->left, level-1) +
getWidth(tree->right, level-1);


#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/*Function protoypes*/
int getWidth(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);

/* Function to get the maximum width of a binary tree*/
int getMaxWidth(struct node* root)
{
int maxWidth = 0;
int width;
int h = height(root);
int i;

/* Get width of each level and compare
the width with maximum width so far */
for(i=1; i<=h; i++)
{
width = getWidth(root, i);
if(width > maxWidth)
maxWidth = width;
}

return maxWidth;
}

/* Get width of a given level */
int getWidth(struct node* root, int level)
{

if(root == NULL)
return 0;

if(level == 1)
return 1;

else if (level > 1)
return getWidth(root->left, level-1) +
getWidth(root->right, level-1);
}

/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lHeight = height(node->left);
int rHeight = height(node->right);
/* use the larger one */

return (lHeight > rHeight)? (lHeight+1): (rHeight+1);
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->right = newNode(8);
root->right->right->left = newNode(6);
root->right->right->right = newNode(7);

/*
Constructed bunary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
printf("Maximum width is %d \n", getMaxWidth(root));
getchar();
return 0;
}

Time Complexity O(N^2)
Space Complexity O(1)
Run Here https://ideone.com/rTjk2


Optimization(Iterative Algorithm)

#include
#include
#include

typedef struct TreeNode {
struct TreeNode *left, *right;
int data;

}TreeNode;


typedef TreeNode * Tree;

/*
*Function which returns maximum width of a binary tree without recursion

We are using level order traversal
*/

int Width(Tree t) {

int width = -1;

if(t != NULL) {

std::list q; //Queue to store tree nodes

q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end of the level

int cur = 0;

while(!q.empty()) {

TreeNode *node = q.front();
q.pop_front();

if(node == NULL) {//delimeter encountered, compare width with cur width and push NULL if q not empty

if(width < cur)
width = cur;

cur = 0;

if(!q.empty())
q.push_back(NULL);

}
else {

cur++;

if(node->left)
q.push_back(node->left);

if(node->right)
q.push_back(node->right);
}
}

}

return width;
}


/*Utilities*/

inline TreeNode * makeTreeNode(int data) {

TreeNode *n = (TreeNode *)calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}


int main() {

/*level 0*/
Tree t = makeTreeNode(10);

/*level 1*/
t->left = makeTreeNode(20);
t->right = makeTreeNode(30);


/*level 2*/
t->left->left = makeTreeNode(40);
t->left->right = makeTreeNode(70);
t->right->left = makeTreeNode(50);
t->right->right = makeTreeNode(60);

/*level 3*/
t->left->left->left = makeTreeNode(70);
t->left->left->right = makeTreeNode(70);
t->left->right->left = makeTreeNode(70);
t->left->right->right = makeTreeNode(70);
t->right->left->left = makeTreeNode(60);
t->right->left->right = makeTreeNode(160);
t->right->right->left = makeTreeNode(60);
t->right->right->right = makeTreeNode(160);

/*level 4*/
t->left->left->left->left = makeTreeNode(70);

printf("%d\n", Width(t));

return 0;
}


Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/rs3tO


Algorithm is Proposed By My Friend Sambasiva He also Runs on Blog On Application of data Structure & Algorithm