recategorized by
19,580 views
56 votes
56 votes

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
recategorized by

7 Answers

Best answer
46 votes
46 votes

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$

edited by
10 votes
10 votes
The given code is wrong.It is not doing any thing
2 votes
2 votes

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

2 votes
2 votes
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:

Related questions

50 votes
50 votes
9 answers
1
go_editor asked Sep 28, 2014
16,244 views
Consider the following rooted tree with the vertex labeled $P$ as the root:The order in which the nodes are visited during an in-order traversal of the tree is$SQPTRWUV$$...