5 Oct 2013

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

No comments:

Post a Comment