GATE CSE 2007 | Question: 46

Question

Consider the following C program segment where $\text{CellNode}$ represents a node in a binary tree:

struct CellNode {
    struct CellNode *leftChild;
    int element;
    struct CellNode *rightChild;
};

int Getvalue (struct CellNode *ptr) {
    int value = 0;
    if (ptr != NULL) {
        if ((ptr->leftChild == NULL) &&
            (ptr->rightChild == NULL))
            value = 1;
        else
            value = value + GetValue(ptr->leftChild)
                      + GetValue(ptr->rightChild);
    }
    return(value);
}

The value returned by $\text{GetValue}$ when a pointer to the root of a binary tree is passed as its argument is:

• A. the number of nodes in the tree

• B. the number of internal nodes in the tree

• C. the number of leaf nodes in the tree

• D. the height of the tree

Comments

this is the leaf node condition right  (root->left==NULL) && (root->right==NULL) and  a tree can have 0 leaf node when it is empty , if single node then root has 1 leaf and if it has 2 nodes then again 1 leaf .and so on ..

---

What if the variable value is static? Would had it affected the result in any way?

---

Same question with same options.

https://gateoverflow.in/2075/gate-cse-2014-set-3-question-41

Answer 1

Answer: C

As the function returns $1$ if and only if any node has both left & right children as $NULL$ (that node is a leaf node). Hence, value gets incremented at each leaf node.

Comments

Typo was corrected.

---

Better to consider a level 2 tree then try to run this function ...

---

Similar question with slight modification: https://gateoverflow.in/1040/gate2004-43

Answer 2

.....

$getvalue(1)$

$i\downarrow$

$value=0+getvalue(1->2)$

                              $ii\downarrow$               $v\uparrow 2$

$value=0+getvalue(2->4)+getvalue(2->5)$

                              $iii\uparrow 1$                                     $iv\uparrow 1$

---

$value=0+getvalue(1->3)$

                              $vi\downarrow$               $ix\uparrow 2$

$value=0+getvalue(3->6)+getvalue(3->7)$

                              $vii\uparrow 1$                                     $viii\uparrow 1$

---

$getvalue(1)$

$i\downarrow$    $x\uparrow 4$

$value=0+getvalue(1->2)+getvalue(1->3)$

                                $v\uparrow 2$                                    $ix\uparrow 2$

---

$A: X$

$B: X$

$C: \checkmark$

$D: X$

Comments

Thanks @KUSHAGRA गुप्ता i'm searching for this kind of tracing 

Answer 3

Let take example, 
 

 

So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes. 
Note that height of the tree is also 3 but it is not correct because in algorithm the part 
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1; 
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.

Answer 4

Assumption: the binary tree is left justified Option a,b,c are absolutely wrong..it measures the height of the tree