Consider the pseudocode given below. The function DoSomething() takes as…
2014
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
- A.
number of internal nodes in the tree.
- B.
height of the tree.
- C.
number of nodes without a right sibling in the tree.
- D.
number of leaf nodes in the tree.
Attempted by 146 students.
Show answer & explanation
Correct answer: D
Key insight: the function counts leaf nodes (nodes with no children).
Base/test: If tree->leftMostChild == NULL, the code sets value = 1. That means this node is treated as a leaf and contributes 1 to the result.
Recursive structure: The call DoSomething(tree->leftMostChild) counts leaves in the node's children, while DoSomething(tree->rightSibling) counts leaves in the node's siblings. Adding them accumulates leaves across the whole tree.
Therefore, when called on the root, the function returns the total number of leaf nodes in the tree.