#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;

}

### Like this:

Like Loading...

*Related*