fork(2) download
copy 
  1. class Node {
  2. 	public Node left;
  3. 	public int data;
  4. 	public Node right;
  5.  
  6. 	public Node(int val) 	{
  7. 		this.data=val;
  8. 	}
  9. }
  10.  
  11. /**
  12.  * Calulate Max Width of a Binary Tree
  13.  * @author Prateek
  14.  *
  15.  */
  16. class MaxWidth {
  17.  
  18. 	/** Calculates width for all levels of the tree
  19. 	 * @param root
  20. 	 * @return max width of Binary Tree
  21. 	 */
  22. 	public int maxWidth(Node root) {
  23.  
  24. 		int level=2;  
  25. 		int curLevel=1;   // root is at level 1
  26. 		int maxLevel=0;   // if root is null max level is 0
  27.  
  28. 		while(curLevel > 0) // for a null node current level will be 0, terminating condition
  29. 		{
  30. 			curLevel = width(root, level++);
  31. 			maxLevel=max(curLevel, maxLevel) ;
  32. 		}
  33. 		return maxLevel;
  34. 	}
  35.  
  36. 	/** 
  37. 	 * @return Number of nodes at a given level
  38. 	 */
  39. 	private int width(Node root , int level ) {
  40. 		if(root == null)
  41. 			return 0;
  42.  
  43. 		if(level==1)
  44. 			return 1;
  45.  
  46. 		return width(root.left , level-1) + width(root.right , level-1) ; 
  47. 	}
  48.  
  49. 	private int max(int curLevel, int maxLevel) {
  50. 		return curLevel > maxLevel ? curLevel : maxLevel ;
  51. 	}
  52.  
  53. 	public static void main(String[] args) {
  54. 		Node root=new Node(52);
  55.  
  56. 		root.left=new Node(30);
  57. 		root.right=new Node(76);
  58. 		root.left.left=new Node(22);
  59. 		root.left.right=new Node(82);
  60. 		root.right.left=new Node(54);
  61. 		root.right.right=new Node(12);
  62.  
  63.  
  64. 		MaxWidth obj=new MaxWidth();
  65. 		System.out.println(obj.maxWidth(root));
  66. 	}
  67. }
  68.  
Success #stdin #stdout 0.06s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/pRHvqb
language:
Java (12.0.1)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!