Consider the following C program segment c struct CellNode { struct CelINode…
2004
Consider the following C program segment
c
struct CellNode
{
struct CelINode *leftchild;
int element;
struct CelINode *rightChild;
}
int Dosomething(struct CelINode *ptr)
{
int value = 0;
if (ptr != NULL)
{
if (ptr->leftChild != NULL)
value = 1 + DoSomething(ptr->leftChild);
if (ptr->rightChild != NULL)
value = max(value, 1 + DoSomething(ptr->rightChild));
}
return (value);
}
The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is
- A.
The number of leaf nodes in the tree
- B.
The number of nodes in the tree
- C.
The number of internal nodes in the tree
- D.
The height of the tree
Attempted by 327 students.
Show answer & explanation
Correct answer: D
Key insight: the function computes the height of the tree measured as the number of edges on the longest path from the given node to a leaf.
Base case: If a node is a leaf (both children NULL), the function returns 0. If the pointer itself is NULL, the function also returns 0 as written.
Recurrence: For a non-leaf node, the function sets value to 1 + DoSomething(child) for each non-null child and takes the maximum. That is, value = max(1 + height(left), 1 + height(right)).
Therefore the returned value equals the longest distance (in edges) from the node to any leaf, i.e., the tree height measured in edges. For example, a single-node tree returns 0; a root with one leaf child returns 1.
Conclusion: the function returns the height of the tree (number of edges on the longest root-to-leaf path).
A video solution is available for this question — log in and enroll to watch it.