Consider the following C program segment where 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 when a pointer to the root of a binary tree is passed as its argument is:
View worked solution
Answer: C
To understand what the function GetValue (written as Getvalue in the definition) returns, let us analyze its recursive behavior on a binary tree node pointed to by ptr:
-
Base Case 1 (Empty Tree):
If
ptr == NULL, the outerifcondition fails, and the function returnsvalue = 0. -
Base Case 2 (Leaf Node):
If both
ptr->leftChild == NULLandptr->rightChild == NULL, the node is a leaf node. In this case, the condition is met, andvalueis set to1. -
Recursive Step (Internal Node):
If the node is an internal node (i.e., it has at least one child), the
elseblock is executed: This recursively sums up the values returned by the left and right subtrees.
Since the function returns 1 for every leaf node and 0 for empty subtrees, the total sum returned at the root is the total number of leaf nodes in the binary tree.
Therefore, the correct option is C.
Free practice · Your answers on this page are not saved.