GATE CS 2023 Q.47: Binary Trees, Binary Search Trees and Balanced Trees

Consider the C function foo and the binary tree shown.

Binary tree with root 10, left child 5 (with left child 3 and right child 8), and right child 11 (with right child 13).

typedef struct node {
  int val;
  struct node *left, *right;
} node;

int foo(node *p) {
  int retval;
  if (p == NULL)
    return 0;
  else {
    retval = p->val + foo(p->left) + foo(p->right);
    printf("%d ", retval);
    return retval;
  }
}

When foo is called with a pointer to the root node of the given binary tree, what will it print?

3 8 5 13 11 10

3 5 8 10 11 13

3 8 16 13 24 50

3 16 8 50 24 13

Official answer and solution

Official answer: C
From: Official GATE 2023 answer key

Solution

Perform a post-order traversal simulation of foo(p), computing subtree sums.

The function foo(p) recursively computes the sum of the subtree rooted at p:

\text{retval} = p\rightarrow\text{val} + \text{foo}(p\rightarrow\text{left}) + \text{foo}(p\rightarrow\text{right})

It prints retval after both subtrees have returned (post-order fashion):

Node 3 (leaf): foo(3) returns $3 + 0 + 0 = 3$ . Prints: 3
Node 8 (leaf): foo(8) returns $8 + 0 + 0 = 8$ . Prints: 8
Node 5 (left child of root): has children 3 and 8. retval = 5 + 3 + 8 = 16. Prints: 16
Node 13 (leaf): foo(13) returns $13 + 0 + 0 = 13$ . Prints: 13
Node 11 (right child of root): has right child 13 (left is NULL). retval = 11 + 0 + 13 = 24. Prints: 24
Node 10 (root): retval = 10 + 16 + 24 = 50. Prints: 50

The complete printed sequence is: 3 8 16 13 24 50.

Final answer

Option (C)

Common trap

Printing node values (3 8 5 13 11 10) instead of the accumulated subtree sums.

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

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 47 of 65
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