The Gateway to Computer Science Excellence
0 votes
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 by Veteran (119k points) | 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

1 Answer

0 votes
Code 2 is fine
by Loyal (5.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,390 answers
198,589 comments
105,443 users