The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
2.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
asked in DS by Veteran (98.8k points)
recategorized by | 2.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

@Adiaspirant ji,

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.

0

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

Ans. - It is a good exercise. Please check diagram on the following link. You will get your answer. 

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

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

2 Answers

+20 votes
Best answer

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. 
answered by Active (2k points)
edited by
0

is it right according to definition you mentioned?

+1
+1
@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.
0
if we are unnable to go to right than how you can we conclude number of leaves......so something is wrong with this problem
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.
0
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 votes

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

Below is function with comments added to demonstrate how function works.

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);

}

 

answered by Loyal (8k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,814 questions
41,799 answers
119,031 comments
41,444 users