class Node {
	public Node left;
	public int data;
	public Node right;

	public Node(int val) 	{
		this.data=val;
	}
}

/**
 * Calulate Max Width of a Binary Tree
 * @author Prateek
 *
 */
class MaxWidth {

	/** 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) ; 
	}

	private int max(int curLevel, int maxLevel) {
		return curLevel > maxLevel ? curLevel : maxLevel ;
	}
	
	public static void main(String[] args) {
		Node root=new Node(52);

		root.left=new Node(30);
		root.right=new Node(76);
		root.left.left=new Node(22);
		root.left.right=new Node(82);
		root.right.left=new Node(54);
		root.right.right=new Node(12);


		MaxWidth obj=new MaxWidth();
		System.out.println(obj.maxWidth(root));
	}
}