Diameter of tree

#1

int diameter(node *temp){
if(temp==NULL){
return 0;
}
if(temp->right==NULL && temp->left==NULL){
return 1;
}
if(temp->right!=NULL && temp->left!=NULL){
return 1 + diameter(temp->right) + diameter(temp->left);
}
if(temp->left==NULL){
return 1+diameter(temp->right);
}
if(temp->right==NULL){
return 1+diameter(temp->left);
}
}

Why isn’t this function returning the correct diameter?

#2

Diameter of a tree is the maximum of these three

  • diameter of left sub-tree
  • diameter of right sub-tree
  • height of tree
    So for calculating the diameter you should follow this
    • find height of left sub-tree
      left_height = height(tree->left)
    • find height of right sub-tree
      right_height = height(tree->right)
      so, height_of_tree = left_height + right_height + 1
    • find diameter of left sub-tree
      left_diameter = diameter(tree->left)
    • find diameter of right sub-tree
      right_diameter = diameter(tree->right)
    • then return the max of these values
      return maximum( height_of_tree, left_diameter, left_diameter)
1 Like