Maximum width of a Binary Tree

Problem Statement: 
   Calculate the Maximum Width of a Binary Tree.

Solution: 

Definition: 
Max Width of a Binary Tree:
               It is the maximum number of nodes at some level of a Binary Tree.

Width of any node is sum of the widths of left sub-tree and right sub-tree where level value reduces to 1 starting from root.

Pls refer to complete Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

/** Calculates width for all levels of the tree * @param root * @return max width of Binary Tree */ public int maxWidth(Node root) { int level=2; int curLevel=1; // root is at level 1 int maxLevel=0; // if root is null max level is 0 while(curLevel > 0) // for a null node current level will be 0, terminating condition { curLevel = width(root, level++); maxLevel=max(curLevel, maxLevel) ; } return maxLevel; } /** * @return Number of nodes at a given level */ private int width(Node root , int level ) { if(root == null) return 0; if(level==1) return 1; return width(root.left , level-1) + width(root.right , level-1) ; }