Consider the following C program segment where CellNode represents a node in a…
2007
Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode
{
struct CellNOde *leftChild;
int element;
struct CellNode *rightChild;
};
int GetValue(struct CellNode *ptr)
{
int value = 0;
if (ptr != NULL)
{
if ((ptr->leftChild == NULL) &&
(ptr->rightChild == NULL))
value = 1;
else
value = value + GetValue(ptr->leftChild)
+ GetValue(ptr->rightChild);
}
return(value);
}
The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:
- A.
the number of nodes in the tree
- B.
the number of internal nodes in the tree
- C.
the number of leaf nodes in the tree
- D.
the height of the tree
Attempted by 131 students.
Show answer & explanation
Correct answer: C
Answer: the number of leaf nodes in the tree.
Reasoning:
Base case: If the pointer is NULL the function returns 0 because value stays 0 and the if(ptr != NULL) block is skipped.
Leaf case: If the node exists and both leftChild and rightChild are NULL the function sets value to 1. That counts this node as one leaf.
Recursive case: For an internal node the function sets value to the sum of GetValue on the left and right children. It does not add 1 for the internal node itself.
Conclusion: Because only leaf nodes produce a value of 1 and internal nodes produce the sum of their children, the function returns the total number of leaf nodes in the tree.
Quick example: A root with two leaf children returns 1 (left) + 1 (right) = 2, matching the number of leaves.