78 views

I want longest path from root to leaf. Then which code is correct among Code-1 or Code-2?

Code-1)

int tree(Struct node *root){
int a=0, b=0,c=0;
if(root==NULL)
return 0;
if((root->left==NULL)&&(root->right==NULL))
return 1;
a=1+tree(root->left);
b=1+tree(root->right);
c=1+max(a,b);
return c;
}

Code-2)

int tree(Struct node *root){
int a=0, b=0,c=0;
if(root==NULL)
return 0;
if((root->left==NULL)&&(root->right==NULL))
return 1;
a=tree(root->left);
b=tree(root->right);
c=1+max(a,b);
return c;
}
in DS | 78 views
+1
Code-1 is definitely not correct
Code-2 Gives kind-of correct answer but not actually correct as in "Path" we see edges but it gives 1+total edges in the path. we can see this by running on the following tree, code 1 returns 5, while code 2 returns 3 Although the correct answer is 2

1

2                      3

4             5
0

@Anuj Mishra

why 1) not correct?

It is calculating from leaf to root

right?

+1
Because on visiting one internal node we're incrementing path length by 2 , one at calculation of a or b other at c
0
yes, I got it

thanks, but networking one not clear

Code 2 is fine
by Loyal (5.7k points)