Consider the pseudocode given below. The function takes as argument a pointer to the root of an arbitrary tree represented by the representation. Each node of the tree is of type .
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 , the value returned by the function corresponds to the
View worked solution
Answer: D
To understand what the function DoSomething(tree) computes, let us analyze how the Left-Child Right-Sibling (LCRS) representation works:
leftMostChildpoints to the first child of the node. If this isNULL, the node has no children in the original tree.rightSiblingpoints to the immediate sibling of the node.
Let us trace the recursive function DoSomething(tree):
- Base Case 1: If
tree == NULL, the function returns0. - Base Case 2: If
tree->leftMostChild == NULL, the node has no children in the original tree. This means the node is a leaf node. Thus,valueis set to1. - Recursive Step 1 (Children): If
tree->leftMostChild != NULL, the node is an internal node. The function recursively counts the leaves in the subtree of its children by callingDoSomething(tree->leftMostChild). - Recursive Step 2 (Siblings): Finally, the function adds the count of leaves from the sibling subtrees by adding
DoSomething(tree->rightSibling).
By combining the leaf counts of the children and the siblings, the function recursively traverses the entire tree and returns the total number of leaf nodes in the tree.
Therefore, the correct option is D.
Free practice · Your answers on this page are not saved.