GATE CSE 2004 | Question: 43

Question

Consider the following C program segment

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

int Dosomething (struct CellNode *ptr)
{
    int value = 0;
    if(ptr != NULL)
    { 
        if (ptr -> leftChild != NULL)
            value = 1 + DoSomething (ptr -> leftChild);
        if (ptr -> rightChild != NULL)
            value = max(value, 1 + Dosomething (ptr -> rightChild));
    }
    return(value);
}

The value returned by the function $\text{DoSomething}$ when a pointer to the root of a non-empty tree is passed as argument is

• A. The number of leaf nodes in the tree
• B. The number of nodes in the tree
• C. The number of internal nodes in the tree
• D. The height of the tree

Comments

Take this tree .

Result for all options will be as follows:

A- 4

B-7

C-3

D-2

Running given code we get 2 as answer . So option D is right

---

Apart from option D, the remaining options talks about counting leaf nodes,internal nodes or total nodes, i guess while counting these nodes we dont need to take maximum value so we can choose the option  D pretty quickly (we take maximum height of left subtree and right subtree as height so option D). is this approach correct?

---

Simply take 1 node tree then Value retured is 0 , Must be D

Answer 1

Correct Option: D

It calculates Height of tree.

Easy way to get this answer .

Draw a tree where all $4$ parameters are different.

Get a Tree for which Height, No of Internal Nodes & No of Leafs are different & Trace out this algorithm.

Comments

The below diagram may make the code easier to understand.

Answer 2

It actually calculates the height of the tree

How I did that: I drew a tree then just tried the algo on this tree and then I modified the tree wisely,  then I tried the algo one more time

Comments

LOL

---

there should be a section called “legend answer” for answers like these :P

---

take just 1 node   *_*

Answer 3

Try to run code on this type of tree:

1.here node at the same level are sibling(are right subtree).

2. The node below are child(left subtree).

It is kind of representaion of n ary tree.

Comments

Your figure can be represented as 

You will get answer as D