Width of a binary tree

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)