Made Easy Test Series:DS

Question

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;
}

Comments

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

---

@Anuj Mishra

why 1) not correct?

It is calculating from leaf to root

right?

---

Because on visiting one internal node we're incrementing path length by 2 , one at calculation of a or b other at c

---

yes, I got it

thanks, but networking one not clear

Answer 1

Code 2 is fine