recategorized by
19,581 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

2 votes
2 votes

Even after getting the fact, that  “value = value + DoSomething(tree->rightSibling);”  this is outside the else, I was getting none as answer.

But the catch is “leftMostChild−rightSibling” this means it is a CBT,  the nodes gets filled from left to right

and hence if there is no left child node, obviously there is no right child node.

We can see the recursion is counting no. of nodes with no left child, so basically it is counting the no of leaves. 

So the answer is: (d) number of leaf nodes in the tree

 

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

}

1 votes
1 votes
Based on the given pseudocode, the function `DoSomething` calculates and returns a value based on the structure of the tree. Let's understand how the function works with an example tree.

Suppose we have the following tree structure:

        A
       / \
      B   C
     / \
    D   E
   /
  F
 

In this tree, each node has a `leftMostChild` pointer pointing to its leftmost child, and a `rightSibling` pointer pointing to its right sibling (a node at the same level).

Let's go through the execution of the `DoSomething` function with the given tree.

1. Initially, we pass the root node "A" to the function: `DoSomething(A)`.

2. The function checks if the tree pointer is not `NULL`. Since the root node is not `NULL`, it proceeds to the next steps.

3. The function checks if the leftMostChild pointer of the root node is `NULL`. In this case, it is not `NULL`, so it moves to the else block.

4. It recursively calls the `DoSomething` function with the leftMostChild of the root node: `DoSomething(B)`.

5. For the node "B," the function again checks if the leftMostChild pointer is `NULL`. In this case, it is also not `NULL`, so it moves to the else block.

6. It recursively calls the `DoSomething` function with the leftMostChild of node "B": `DoSomething(D)`.

7. For the node "D," the function checks if the leftMostChild pointer is `NULL`. In this case, it is `NULL`, so it sets `value = 1`.

8. It returns `value` (which is 1) back to the previous call, which was `DoSomething(B)`.

9. Now, the function calculates `value = value + DoSomething(tree->rightSibling)`. Since node "B" has a right sibling "C," it calls `DoSomething(C)`.

10. For node "C," the function checks if the leftMostChild pointer is `NULL`. In this case, it is `NULL`, so it sets `value = 1` for node "C."

11. It returns `value` (which is 1) back to the previous call, which was `DoSomething(A)`.

12. Finally, for node "A," the function calculates `value = value + DoSomething(tree->rightSibling)`. Since node "A" has a right sibling `NULL`, it returns 0 for the right sibling.

        A
       / \
      B   C
     / \
    D   E
   /
  F
 

13. The function returns the final `value`, which is `1 + 0 + 1 = 2`.

So, in this example, when the root node "A" is passed to the `DoSomething` function, the returned value is 2.

Please note that the pseudocode doesn't explicitly mention the purpose or meaning of the returned value, so its interpretation would depend on the specific context or intention of the code.
edited by
Answer:

Related questions

50 votes
50 votes
9 answers
1
go_editor asked Sep 28, 2014
16,266 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$$...