**Problem:**Given a binary tree, write a method to get the width of the given binary tree. Width of a tree is maximum of widths of all levels in the tree.

**Solution:**Use level order traversal.

**Implementation:**

int BSTree::getWidth()

{

int maxW = -1;

if(!root)

return maxW;

std::queue<Node*> q[2];

bool turn = 0;

q[turn].push(root);

while(!q[turn].empty())

{

int currW = q[turn].size();

if(maxW < currW)

maxW = currW;

while(!q[turn].empty())

{

Node *temp = q[turn].front();

if(temp->left)

q[!turn].push(temp->left);

if(temp->right)

q[!turn].push(temp->right);

q[turn].pop();

}

turn = !turn;

}

return maxW;

}

**Complexity:**O(n)

## No comments:

## Post a Comment