The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
2.1k 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 (98k points)
recategorized by | 2.1k views
I am not getting this point how we are considering leftmost child same as left child of a node.
what will be the the answer for the no. of nodes without a right sibling?

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

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

+16 votes
Best answer

Here, the condition for count value = 1 is

if (tree→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).
  • ∴ 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 (2.1k points)
selected by

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 .
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 Boss (5.4k 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

29,006 questions
36,838 answers
91,329 comments
34,718 users