GATE CSE 2014 | Set 3 | Question: 41

Question

Consider the pseudocode given below. The function $DoSomething()$ takes as argument a pointer to the root of an arbitrary tree represented by the $leftMostChild-rightSibling$ representation. Each node of the tree is of type $treeNode$.

typedef struct treeNode* treeptr; 

struct treeNode 
{ 
    treeptr leftMostChild, rightSibling; 
}; 

int DoSomething (treeptr tree) 
{ 
    int value=0; 
    if (tree != NULL) { 
        if (tree->leftMostChild == NULL) 
            value = 1; 
        else 
        value = DoSomething(tree->leftMostChild); 
        value = value + DoSomething(tree->rightSibling); 
    } 
    return(value); 
} 

When the pointer to the root of a tree is passed as the argument to $DoSomething$, the value returned by the function corresponds to the 

• A. number of internal nodes in the tree.
• B. height of the tree.
• C. number of nodes without a right sibling in the tree.
• D. number of leaf nodes in the tree

Comments

Tree                        
                     
            [A]                                    
           /   \                                 
          /     \                     
        [B]     [C]                               
                                                
 

DoSomething(A)
   │
   └───> Calls DoSomething(B)  [via leftMostChild]
            │
            ├───> 1. Sees B has no children (value = 1)
            │
            └───> 2. Calls DoSomething(C)  [via rightSibling]
                     │
                     ├───> 1. Sees C has no children (value = 1)
                     │
                     └───> 2. Calls DoSomething(NULL)  [via rightSibling] ──> Returns 0
                     │
                     └─> Returns (1 + 0) = 1
            │
            └─> Returns (1 + 1) = 2
   │
   └───> Calls DoSomething(NULL)  [via rightSibling of A] ──> Returns 0
   │
   └─> Final Return (2 + 0) = 2
so D is correct

---

leftMostChild → first child

---

If $X$ has no leftMostChild, then $X$ has zero children in total !!

Answer 1

Here, the condition for count value $= 1$ is

if ($tree \rightarrow  leftMostchild == Null)$

• so, if there is no left-most child of the tree (or the sub-tree or the current node called in recursion)
•  Which means there is no child to that particular node (since if there is no left-most child, there is no child at all as per the tree representation given).
• $\therefore$ the node under consideration is a leaf node.
• The function recursively counts, and adds to value, whenever a leaf node is encountered.

So, The function returns the number of leaf nodes in the tree. Answer is $D$

Comments

its not valid leftmostchild rigthsibling representation thats why you are getting wrong answer

---

@Dknights ans is 2 only

at first you will move towards the left child that will return you 1 because its left node is null , now value is 1 and further go for right child this will also give you 1 because its left node is also null and thus it will return value 2 .(right child will not check its right child becuase its left is only null)

---

actually the problem here is the damn indentation note the line 

value = value + DoSomething(tree->rightSibling); is not in the scope of else this is the main problem 

Answer 2

The given code is wrong.It is not doing any thing

Comments

😁

---

👍

---

🤣

Answer 3

Even after getting the fact, that  “value = value + DoSomething(tree->rightSibling);”  this is outside the else, I was getting none as answer.

But the catch is “leftMostChild−rightSibling” this means it is a CBT,  the nodes gets filled from left to right

and hence if there is no left child node, obviously there is no right child node.

We can see the recursion is counting no. of nodes with no left child, so basically it is counting the no of leaves. 

So the answer is: (d) number of leaf nodes in the tree

 

Comments

The question statement clearly mentions it as an arbitrary tree. Merely filling up of nodes from left to right is not sufficient for a CBT. It must first be a binary tree for which the number of child nodes can be at most 2. But for an arbitrary tree we should also consider cases where there are more than 2 children per node. Hence, I feel we cannot approach question assuming it is a CBT in all cases.

---

you are correct and I have dry run this code on tree in which some internal nodes only have right child and its working,value =1 helps, we don't traverse to right child but its number of nodes is updated by ifs first statement.

Answer 4

I want to say a thing that its a C code and in C in if or else block if you give more than 1 statement its only the first statement that is considered to be in that block...some people posted here as if there is 2 statements in thw ekse block but actually there is only 1.

here after else word  2 statements r there..

only first will get executed in else block.That is "value=DoSomething(tree->lestMostChild)"

this line=>> "value=value+DoSomething(tree->RightSibiling)" is not in else block...and its always executed in the very first " if " block..

 

THIS IS HOW YOU SHOULD SEE THE CODE:::::>>>

typedef struct treeNode* treeptr; 

struct treeNode 
{ 
    treeptr leftMostChild, rightSibling; 
}; 

int DoSomething (treeptr tree) 
{ 
    int value=0; 
    if (tree != NULL) { 
        if (tree->leftMostChild == NULL) 
              value = 1; 
        else 
              value = DoSomething(tree->leftMostChild);

        value = value + DoSomething(tree->rightSibling); 
    } 
    return(value); 
} 

 

 

 

so in one line if given pointer is null make value 0 and return value; if its not null but leftmostchild is null that means its a leaf so make value=1 and go for rightsibilings adding if they r leaf too...and if given pointer has a leftmostchild that call that function for the leftmostchild...

 

umtimately whole tree is traversed...only value gets to be 1 if nide is leaf and all such 1's are added...

Comments

The code above will only traverse till node G and return 1. But for the right sibling of node b, it won't.traverse ( please correct me if I'm wrong)

---

Correct observation about this line.

        value = value + DoSomething(tree->rightSibling); 

thanks.

Answer 5

all the option are wrong i have code this

#include<stdlib.h>
using namespace std;
struct node
{
    int key;
    struct node *left, *right;
};

struct node *newNode(int item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d \n", root->key);
        inorder(root->right);
    }
}

struct node* insert(struct node* node, int key)
{
    
    if (node == NULL) return newNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    return node;
}
int DoSomething (node* tree)
{
    int value=0;
    if (tree != NULL) {
        if (tree->left == NULL)
            value = 1;
        else
        value = DoSomething(tree->left);
        value = value + DoSomething(tree->right);
    }
    return(value);
}

int main()
{

    struct node *root = NULL;
    root = insert(root, 10);
    insert(root, 5);
    insert(root, 4);
    insert(root, 15);
    insert(root, 13);
    insert(root, 14);
    insert(root, 16);

    int a=DoSomething (root);
    printf("%d",a);
    return 0;
}
it is returing 4 but the leaf are 3 only rest all option before are eliminated

Answer 6

Based on the given pseudocode, the function `DoSomething` calculates and returns a value based on the structure of the tree. Let's understand how the function works with an example tree.

Suppose we have the following tree structure:

        A
       / \
      B   C
     / \
    D   E
   /
  F
 

In this tree, each node has a `leftMostChild` pointer pointing to its leftmost child, and a `rightSibling` pointer pointing to its right sibling (a node at the same level).

Let's go through the execution of the `DoSomething` function with the given tree.

1. Initially, we pass the root node "A" to the function: `DoSomething(A)`.

2. The function checks if the tree pointer is not `NULL`. Since the root node is not `NULL`, it proceeds to the next steps.

3. The function checks if the leftMostChild pointer of the root node is `NULL`. In this case, it is not `NULL`, so it moves to the else block.

4. It recursively calls the `DoSomething` function with the leftMostChild of the root node: `DoSomething(B)`.

5. For the node "B," the function again checks if the leftMostChild pointer is `NULL`. In this case, it is also not `NULL`, so it moves to the else block.

6. It recursively calls the `DoSomething` function with the leftMostChild of node "B": `DoSomething(D)`.

7. For the node "D," the function checks if the leftMostChild pointer is `NULL`. In this case, it is `NULL`, so it sets `value = 1`.

8. It returns `value` (which is 1) back to the previous call, which was `DoSomething(B)`.

9. Now, the function calculates `value = value + DoSomething(tree->rightSibling)`. Since node "B" has a right sibling "C," it calls `DoSomething(C)`.

10. For node "C," the function checks if the leftMostChild pointer is `NULL`. In this case, it is `NULL`, so it sets `value = 1` for node "C."

11. It returns `value` (which is 1) back to the previous call, which was `DoSomething(A)`.

12. Finally, for node "A," the function calculates `value = value + DoSomething(tree->rightSibling)`. Since node "A" has a right sibling `NULL`, it returns 0 for the right sibling.

        A
       / \
      B   C
     / \
    D   E
   /
  F
 

13. The function returns the final `value`, which is `1 + 0 + 1 = 2`.

So, in this example, when the root node "A" is passed to the `DoSomething` function, the returned value is 2.

Please note that the pseudocode doesn't explicitly mention the purpose or meaning of the returned value, so its interpretation would depend on the specific context or intention of the code.

Comments

For the node "D," the function checks if the leftMostChild pointer is `NULL`. In this case, it is `NULL`, so it sets `value = 1`.

what do you mean by the clearly in your diagram "D" has a leftmost child which is "F" right?

---

Yeah man what did he mean by that D has a leftMostChild as F..??