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

nomenclature of ttree is different here

left child → lefmost child

right child → right sibling

so in option d no. of leave node  means no. of nodes which has no child(leftmost child)

---

One of the most easiest explaination 

https://gateoverflow.in/2075/gate-cse-2014-set-3-question-41?show=407242#a407242

---

@Sachin Mittal 1

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

@Kalpish: Did you check your explanation for a TREE where some of the internal node also does not have a LEFT child ??

I computed and found that the algorithm NOT only returns number of leaves BUT also the nodes which don't have a left child including leaves as leaves also don't have left child.

Check for this tree:  ((N,A,B),C,(E,D,N)) where order pair (X,Y,Z) represents left child,root and right child respectively.

Please check If I missed smething !!

According to you this must return 2 but it returns 3 when I compute.

---

i checked o/p of  a TREE where some of the internal node also does not have a LEFT child after you commented and I am getting exact desired o/p as it should be please verify once... please upload the picture for tree you are getting issue within your above example(mentioned by you ) I am getting 4 leaf node as I interpreted your text ...but may b the interpretation is wrong 
I tried Algo or following graph and got 2 as the output 
Notice: while running the algo be careful that 

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

else will execute only 

value = DoSomething(tree->leftMostChild); 

wthr condition true or false 

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

code will surely execute 

---

@sorry Kalpish :But i still dint get this.I will tell you where.

when it checks for

if (tree->leftMostChild == NULL) 
            value = 1;

it sets value to 1 whenever there is no left node AND then recursively calls RIGHT child for which it will do the same. Tell me If I am doing SOME mistake here. BECAUSE here is the only point I am confused because according to this "if" condition ,it adds 1 to value for each node WITHOUT left child.

Please explain this "if condition" in particular.

Thanx for your valuable time and help.

---

by looking at this lines we can guess ans

if (tree->leftMostChild == NULL) 
            value = 1;

---

why you've assumed that if no left subtree then there'll not be right sub tree?
this algo also adds 1 for that internal node which dont have left child but have right child....
tell me where i'm mistaking?

---

due to the tree representation given in question. It uses only left most child and all other child nodes become its sibling. So, no leftmost implies no child at all.

---

sir but from which line we can make out that "no leftChild then no child" ?
i was doing consedering leftmostChild as left sibbling and right sibbling is right sibbling (as name suggests).
really confused :/

---

if there is just one child node - it is the leftmost child.

If there are two child nodes - one becomes the left most and other becomes its sibling

And so on.

So, no leftmost child means no child nodes at all..

---

Note: leftmostchild-rightshibling is a representation. We should not consider this representation as the original tree structure.

ref : https://xlinux.nist.gov/dads//HTML/binaryTreeRepofTree.html

---

@Debashish Deka  

U r right actually we use it for constructing a binary tree from the general tree.

---

this can't be the answer bcz when we execute code then it will not reach to the end node of siblings. the compiler only reached till first sibling and then condition will return and terminate..

---

Can't one of the right siblings of a leftmost node which doesn't have children - have children? Please have a look at this tree below? Will the algorithm compute the no of leaves=2+1+2=5, as in this case?

---

Here no of leaves is 6. And algo will return 6

---

@ kalpish, Sandeep_Uniyal sir i also still din't get this.plz help me....

---

is it right according to definition you mentioned?

---

@eyeamgj Watched the video. It was helpful but Sir took statement 1 and 2 both under else condition. I think only statement 1 will be executed for the else part and statement 2 should be executed irrespective of whether the node has leftmost child or not. I did it that way and the answer is coming.

---

if we are unnable to go to right than how you can we conclude number of leaves......so something is wrong with this problem

---

What Sir did was, if the node has no left child he returned the value=1. But I am saying that why should we neglect the 2nd statement after "else"? That doesn't come under else part right? The immediate statement after else should only come.

---

1. If (tree->leftmost child==Null)

2. value=1;

3. Else

4. value= Dosomething(tree->leftMostchild);

5. value=value+Dosomething (tree->rightsibling);

If a node doesn't have a leftMostchild i.e. line no. 1 is true then it will execute line no. 2 and 5.

If a node has a leftMostchild i.e. line no. 3 is true then it will execute line no. 4 and 5.

The line 5 does not come under the else condition is what I am saying because there are no braces enclosing the two statements after else. Don't you think so?

---

ya u seems right i just iterated the program once again and found 6 number of leaves (value =6)for the tree mentioned in video(how much value u got for value?)...........so conclusion is that  answer is no. of leaves...

---

Yes I got 6 too :D and yes..no. of leaves it is

---

thankyou so much for eliminating the mistake

---

both the statements will not come under else condition the second statement will get executed for even leafs and non leafs also as there was no paranthesis {    } only one statment is executed after else so sir was wrong in this video .

---

In case of a right skewed tree, answer is not coming as a number of leaf node.

eg. If consider a right skewed tree with 3 nodes, then the answer I am getting is 3 not 1(as 1 is the no. of leaf node in right skewed tree).

Please clear my doubt.

---

We need to convert the right skewed tree into "left-most child right sibling" representation. What are you getting? I got a structure that is similar to a left skewed tree.

Ref: https://www.geeksforgeeks.org/left-child-right-sibling-representation-tree/

---

@kalpish

It will not count all the leaf nodes. In left child there can be many right siblings connected to it and that right siblings are not counted in this program. That all right siblings may or may not be leaves, but if they are leaf they will not be counted in the program.

@Arjun sir verify ans please

---

For a leaf node left child and right child is NULL but here only left child is null . then how it count number of leaf nodes of the tree.

---

can someone traverse the code in this tree, i am getting the answer as 3?

Answer 2

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

Comments

It does none of the option provided.

---

Hey I would just like to point out that this line doesn't comes under else part:

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

This line is executed everytime. Try to trace out the function again and it will count root nodes. Its just that the indentations are confusing in this question

Answer 3

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)

Answer 4

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