GATE CSE
First time here? Checkout the FAQ!
x
+16 votes
1.8k 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 (87.2k points)  
recategorized by | 1.8k 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?

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

+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 (2.1k points)  
selected by
@Debashish Deka  

U r right actually we use it for constructing a binary tree from the general tree.
this can't be the answer bcz when we execute code then it will not reach to the end node of siblings. the compiler only reached till first sibling and then condition will return and terminate..

Can't one of the right siblings of a leftmost node which doesn't have children - have children? Please have a look at this tree below? Will the algorithm compute the no of leaves=2+1+2=5, as in this case?

Here no of leaves is 6. And algo will return 6

kalpishSandeep_Uniyal sir i also still din't get this.plz help me....

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 (4k points)  


Top Users Sep 2017
  1. Habibkhan

    6504 Points

  2. Arjun

    2254 Points

  3. Warrior

    2234 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. Bikram

    1726 Points

  7. SiddharthMahapatra

    1718 Points

  8. makhdoom ghaya

    1680 Points

  9. A_i_$_h

    1668 Points

  10. rishu_darkshadow

    1554 Points


25,999 questions
33,568 answers
79,491 comments
31,035 users