CareerCup

get the height of the tree , h, and max width of tree will be (2^h) -1.

public int height(Node root){
if(root.val != NULL)
return 1+max(height(root.getLeft()), height(root.getRight()) ;
return 0;

}

public int findWidth(Node root){
int h = height(root);
return ((2^h)-1);

}

Traverse the tree; Use an extra int array to count width of each level;
Finally find the largest width.
Is there a way without extra space usage?

step 1: find the height of the tree
step 2: do the level order traversal and keep a count of number of nodes at each level
step 3: print the max node count after whole traversal tree is over

Should we use Breadth First Search(BFS) for this case with little modification? In this case, we will visit each node exactly once.

Enqueue root node
set count=1
while queue not empty
do
tmp_cnt =0
while I<count
   Do
     Dequeue node
     I++
     Increment tmp_cnt
     Enqueue the child nodes
  Done
if tmp_cnt > max_cnt 
   Max_cnt = tmp_cnt
count = tmp_cnt
done

return max_cnt

Use BFS, keep track of number of nodes on each level

1. set maximum = 1
2. Push(1, Root node)
3. Pop(number of nodes on next level, node list)
4. Sum up the number of child nodes for each node in the node list.
5. if sum > maximum, set maximum to sum
6. Push(sum, child nodes)
7. Go to 3.

Create a struct NL that stores a node pointer and a level (int)
Use a queue of NLs

Struct NL {
Node* n, int level }

Int MaxWidth (Node* root)
{
Queue q = new queue();
NL nl1 { n=root, level =1)
NL prev, curr;
q.enqueue(nl1);
Int currcount, MAX;
MAX = 0;

While (!q.isEmpty())
{
Curr = q.dequeue();
If (prev!=null && curr.level == prev.level){
currcount ++;
}
Else
{
Currcount = 1;
}
If (currcount > MAX) MAX = currcount;
If (curr.n->l)
{
NL nl2 { n = curr.n->l, n.level+1 };
q.enqueue(nl2);
}
If (curr.n->r)
{
NL nl2 { n = curr.n->r, n.level+1 };
q.enqueue(nl2);
}
Prev = curr;
}
Return MAX;
}