GATE CSE
First time here? Checkout the FAQ!
x
+10 votes
1.4k 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 Algorithms by Veteran (77.2k points)   | 1.4k 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?

2 Answers

+13 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 (2k points)  
selected by
@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.
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 (3.2k points)  
Answer:

Related questions



Top Users May 2017
  1. akash.dinkar12

    3292 Points

  2. pawan kumarln

    1652 Points

  3. sh!va

    1650 Points

  4. Arjun

    1424 Points

  5. Bikram

    1372 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1142 Points

  8. Angkit

    1044 Points

  9. LeenSharma

    904 Points

  10. srestha

    718 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    458 Points

  2. Arnab Bhadra

    402 Points

  3. pawan kumarln

    278 Points

  4. Ahwan

    236 Points

  5. bharti

    194 Points


22,786 questions
29,121 answers
65,184 comments
27,661 users