NOTE_C/DS_1_27

Question

Consider the following functions foobar(), which takes a binary tree as input:

int foobar (struct node * root)

{

     if(!root) return 0;

     if(!root → left && !root → right) return 10;

     else

     {

           int i = foobar (root → left);

           int j = foobar (root → right);

           return (i+j);

     }

}

What does the above function foobar compute ?

(A) sum of internal nodes of the binary tree

(B) number of leaves of the binary tree

(C) sum of leaves of the binary tree

(D) none of these

Comments

IF instead of  "if(!root → left && !root → right) return 10;" is was "if(!root → left && !root → right) return 1;"

then i think the answer is B (no.of leaf nodes).

---

if(! root → left && ! root → right) return 1;

This implies that if the node root doesn't have right or left child then the function returns 1. This means on leaf nodes which don't have right or left child  it returns 1. For all the other nodes which have atleast one child, we keep calling its descendants recursively.

Answer 1

For each node having (root → left == NULL && root → right == NULL) i.e. LEAF NODE program returns 10.

So the value foobar computes is 10*(number of leaves of the binary tree)

Hence, D is the correct answer.

In a similar fashion, if you replace return(i+j) with return(i+j+$A$) it will compute $A$*(number of internal nodes of the binary tree)

where, $A$ is any constant

Comments

Thank you @shreyansh jain