Find the diameter of a binary tree

Diameter of a binary tree

Diameter of a tree is the maximum distance between any of its two nodes. In the above diagram the nodes used to calculate the diameter of tree is highlighted in red color.

Let us write a c program to find the width  of the binary tree. We shall use recursion to solve this algorithm.

Lets us define a function called Max which returns a max of two variables.

int max(int a, int b)

{

   return (a > b ? a : b);

}

struct BTreeNode 

{

 struct BTreeNode  *left;

 struct BTreeNode  *right;

 int data;

};

int TreeWidth(struct BTreeNode *root, int *pWidth)

{

   int left, right;

   //If the root is null, return the height as 0

   if(!root)

       return 0;

   //Get the height of the left sub tree

   left = TreeWidth(root->left,pWidth);

   //Get the height of the right sub tree

   right = TreeWidth(root->right,pWidth);

   

   /*Compare the previous width with the sum of left and right sub tree and store the max of the two values as the new width*/

   * pWidth = max(* pWidth , (left + right));

   

   //add one to the height of the sub tree and return as the new    height

   return max(left, right) + 1;

}