edited by
8,467 views
29 votes
29 votes

Consider the following C program segment where $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 $GetValue$ when a pointer to the root of a binary tree is passed as its argument is:

  1. the number of nodes in the tree

  2. the number of internal nodes in the tree

  3. the number of leaf nodes in the tree

  4. the height of the tree

edited by

4 Answers

Best answer
28 votes
28 votes

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.

edited by
5 votes
5 votes

.....

$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$

1 votes
1 votes

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'.

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

Related questions

17 votes
17 votes
3 answers
1
29 votes
29 votes
3 answers
2
Kathleen asked Sep 21, 2014
31,605 views
The maximum number of binary trees that can be formed with three unlabeled nodes is:$1$$5$$4$$3$
26 votes
26 votes
4 answers
3
Kathleen asked Sep 21, 2014
25,723 views
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height $h$ is:$2^h -1$$2^{h-1} -1$$2^...