5 Oct 2013

Diameter of a Binary Tree

Problem Statement: 
   Find the diameter of the given Binary Tree.



Solution : 

Definition : 
Diameter of Binary Tree: It is the value of the longest  number of nodes from one leaf of the tree to other. This path from one leaf to the other may or may not include the root of the tree.

For every node in the tree we calculate
1. left diameter
2. right diameter
3. left height
4. right height

With the above parameters 3 cases arises for every node (we will call the node in consideration as "Root").
Case 1:  Root is not included and diameter of the left child is maximum.
Case 2 : Root is not included and diameter of the right child is maximum.
Case 3 : Sum of Left Height and Right Height and Root contributes to maximum compared to above cases.


Refer to 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
31
        /**
   * Subroutine to calculate diameter
   * @param root
   * @return diameter
   */
 public int diameter(Node root){
  if(root==null)
   return 0;

  int lHeight=height(root.left);
  int rHeight=height(root.right);

  int ldiameter=diameter(root.left);
  int rdiameter=diameter(root.right);

  return max(lHeight + rHeight + 1 , max(ldiameter, rdiameter)) ;
 }

 /**
  * @param root of the tree
  * @return height of the tree
  */
 public int height(Node root) {
  if(root == null)
   return 0;

  int lHeight=height(root.left);
  int rHeight=height(root.right);

  return max(lHeight,rHeight) + 1;
 }

1 comment:

  1. Hi I am so happy I found your blog page, I really found you by error, while I was browsing onn Yahoo for something else, Anyways I
    am here now and would just like to say kudos for a incredible post and a all round entertaining bloog (I
    also love the theme/design), I don’t have time too rad
    it all at the moment but I have savrd it and also added in your RSS feeds, so
    when I have time I will be back to read much more,
    Please do keep uup the fantastic jo.

    Here is my webpage - online education degree australia

    ReplyDelete