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