Diameter of btree

#1

what will be the complexity of use following code for finding height?
int dia=0;//global variable
int diameter(node* root)
{
if(root==NULL)
return 0;
int lh=diameter(root->left);
int rh=diameter(root->right);
dia=max(dia,(lh+rh));
return max(lh,rh)+1;
}

#2

hello @POORVI_SAXENA
it will be O(n) .
because we are just traversing the given tree

#3

for finding diameter*

#4

why is the complexity of code below O(n^2)

int diameter(node* root)
{
if(root is null)
return 0;
int h1=height(root->left);
int h2=height(root->right);
return max((h1+h2), max( diameter(root->left), diameter(root->right));
}

#5

the first one was bottom up where we were using child result to compute the parent result and then progating the result to the next parent.

but here for each node we r calling for diameter function .
so if total n node will be there. we will work n^2 time.

best way to find these type of time complexity is to imagine the given tree as a skew tree

1 Like