Question

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:

Accepted Answer

The correct answer is (C) the number of leaf nodes in the tree. The function adds 1 exactly when it reaches a node with both children NULL (a leaf), and otherwise just sums the results from both children (contributing nothing itself). Recursively, this sums up to the total count of leaf nodes in the tree.

Explanation