Max breadth of a binary tree

#include <stdio.h>
#include <stdlib.h>
#include <list>

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<Tree> 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;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s