GATE CS 2014 Set 3 Q.51 (CS Q.41): Binary Trees, Binary Search Trees and Balanced Trees

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.

struct treeNode {
    treeptr leftMostChild, rightSibling;
};
typedef struct treeNode* treeptr;

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

number of internal nodes in the tree.

height of the tree.

number of nodes without a right sibling in the tree.

number of leaf nodes in the tree.

Official answer and solution

Official answer: D
From: Official GATE 2014 answer key

Solution

Trace the recursive structure of DoSomething on the leftmost-child right-sibling tree representation.

In the leftMostChild-rightSibling representation of a general tree:
- node->leftMostChild points to the first child of the node.
- node->rightSibling points to the next sibling of the node at the same hierarchical level.
Examine DoSomething(tree):
- If tree == NULL, the function returns $0$ .
- If tree != NULL:
  - Case 1: tree->leftMostChild == NULL.
    This means the current node has no children in the original multi-way tree, so it is a leaf node. Here value = 1.
  - Case 2: tree->leftMostChild != NULL.
    The node is an internal node. The call DoSomething(tree->leftMostChild) visits the first child and recursively counts all leaf nodes within the subtree rooted at that child.
  - Finally, value = value + DoSomething(tree->rightSibling) recursively traverses and accumulates the leaf counts across all siblings at that level.
Thus, every leaf in the original tree contributes exactly $1$ to the total sum, while internal nodes contribute $0$ directly and propagate the sum of their subtrees.

Therefore, the function returns the number of leaf nodes in the tree (option D).

Final answer

Common trap

Confusing the binary tree representation with the original multi-way tree it represents.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 3
Question: 51 of 65, printed as CS Q.41
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source