4.9k views

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

1. number of internal nodes in the tree.
2. height of the tree.
3. number of nodes without a right sibling in the tree.
4. number of leaf nodes in the tree
in DS
recategorized | 4.9k views
0
I am not getting this point how we are considering leftmost child same as left child of a node.
0
what will be the the answer for the no. of nodes without a right sibling?
+1

Q. -> I am not getting this point how we are considering leftmost child same as left child of a node.

Ans. - In Binary Tree Left Child is same as left most child But in k-ary tree 'left most child' is first child of a given node from left side. I hope this helps.

+3

Q. ->what will be the the answer for the no. of nodes without a right sibling?

https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree

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

0
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).

0
Sir u r right actually it is not doing any of the given options.It is just returning value 2
0
No.

It will return the number of leaf in the tree.

In case of skewed tree-- in left child right sibling representation, no right sibling are there for any node. At the last level one leaf is present which will return 1.
+2
One thing to notice here is that "only one statement is present inside 'else'. And second statement (i.e. value= value+ dosomething(tree-->rightsibling); ) runs every time whenever tree!=NULL.

I mention it because somewhere the question is treated in the wrong way(by considering two statements inside else) and according to that no option is correct..
0

Look at the following representations:

RHS is left child Right-Sibling representation. Those nodes which are leaf nodes in LHS tree, have become nodes without left child in RHS tree.
For example $N,O,I,JC,D,P,Q,F,M$ are leaf nodes in LHS tree, and if you notice then these nodes don't have Left Child in equivalent RHS Left Child Right-Sibling Tree, hence this code given above is counting the number if leaf nodes in the tree.

0
thank  you very much  , wasted half an hour on this question and then realized  that the last statement isn't a part of the else block

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$

by Active (2k points)
edited
0
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
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?
0
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...
0
Yes I got 6 too :D and yes..no. of leaves it is
0
thankyou so much for eliminating the mistake
0
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 .
0
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).

0

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.

0
@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.

0
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.
The given code is wrong.It is not doing any thing
by Junior (771 points)
+1

It does none of the option provided.

0

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

+1 vote

The function counts leaf nodes for a tree represented using leftMostChild-rightSibling representation.

 int DoSomething (treeptr tree) {     // If tree is empty, 0 is returned     int value = 0;     // IF tree is not empty     if (tree != NULL)     {         // IF this is a leaf node, then values is initialized as 1         if (tree->leftMostChild == NULL)             value = 1;         // Else value is initialized as the value returned by leftmost         // child which in turn calls for the other children of this node         // Using last call "value = value + DoSomething(tree->rightSibling);"         else             value = DoSomething(tree->leftMostChild);         // Add value returned by right sibling         value = value + DoSomething(tree->rightSibling);     }     return(value); }
by Loyal (9.5k points)
+2

All the given options are wrong

0
You have written wrong program.Else block(in question given) only contain the statement which is just next to it .And you have included both the statementz in else block.
+1 vote
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
by Junior (529 points)

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...

by (129 points)
0

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)

1
2