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

1st if calculates the height of the left subtree and 2nd if computes the height of the right subtree and takes the max of (height of left subtree, height of right subtree).

---

as program is comparing values from left and right sub tree , hence result can not be count of leaf , internal nodes , total nodes hence option a,b,c can be  eliminated

---

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

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

Wow ... Thug life (y) ...

---

 

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

what kind of explanation is this? :D :D

---

LOL

---

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

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