The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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;
            value = value + GetValue(ptr->leftChild)
                      + GetValue(ptr->rightChild);

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

asked in DS by Veteran (59.5k points)
edited by | 1.4k views

2 Answers

+19 votes
Best answer

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.

answered by Boss (34k points)
edited by
But are all nodes being visited?

Oh, I didn't see the question here. The else statement is as follows in the question paper:

value = value + getValue(ptr->leftChild) + getValue(ptr->rightChild)
It was a typo. Corrected now. But beware of such stuffs in GATE :)
Please remove the picture attached with this question (as it still has the typo). Ya, I know what IIT-K did this year. :)
whats the typo in this question. It seems to be correct. What am i missing???
Typo was corrected.
Better to consider a level 2 tree then try to run this function ...
–8 votes
Assumption: the binary tree is left justified Option a,b,c are absolutely measures the height of the tree
answered by Boss (14.2k points)

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

38,039 questions
45,534 answers
48,853 users