IAE Academy

GATE 2023 CS Q.47: solution and answer

GATE 2023 · CSQ.47 · 2 marks · MCQ

Consider the C function foo and the binary tree shown.

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?

GATE 2023 CS question 47: A binary tree with root node 10.Tap to open full size
Figure from the GATE 2023 CS paper. It is part of the question.
Figure description

A binary tree with root node 10. Root's left child is 5, root's right child is 11. Node 5's left child is 3 and right child is 8 (5 has no other children). Node 11's right child is 13; node 11 has no left child. Nodes 3, 8, and 13 are leaves with no children. Edges: 10->5 (left), 10->11 (right), 5->3 (left), 5->8 (right), 11->13 (right).

  1. (A)

    3 8 5 13 11 10

  2. (B)

    3 5 8 10 11 13

  3. (C)

    3 8 16 13 24 50

  4. (D)

    3 16 8 50 24 13

Answer and solution

ANSWER

Option C — the program prints 3 8 16 13 24 50

Official answer: CSource: Official answer key, GATE 2023 CS (IIT Kanpur)

  1. The printf executes only after BOTH recursive calls foo(p->left) and foo(p->right) have returned and retval has been fully computed, so the print order follows post-order traversal (left subtree, then right subtree, then the current node) — and each printed value is the SUM of that node's entire subtree, not the node's own stored value.

  2. Leaf node 3 (left child of 5): retval = 3 + foo(NULL) + foo(NULL) = 3 + 0 + 0 = 3. Prints "3".

  3. Leaf node 8 (right child of 5): retval = 8 + 0 + 0 = 8. Prints "8".

  4. Node 5: foo(left = 3) runs first and prints "3"; then foo(right = 8) runs and prints "8"; then retval = 5 + 3 + 8 = 16. Prints "16". Output so far: 3 8 16.

  5. Leaf node 13 (right child of 11; 11 has no left child): retval = 13 + foo(NULL) + foo(NULL) = 13 + 0 + 0 = 13. Prints "13".

  6. Node 11: foo(left = NULL) returns 0 with no print (base case just returns, no printf runs when p == NULL); then foo(right = 13) runs and prints "13"; then retval = 11 + 0 + 13 = 24. Prints "24". Output so far: 3 8 16 13 24.

  7. Node 10 (root): foo(left = 5) runs to completion first, producing prints 3, 8, 16; then foo(right = 11) runs to completion, producing prints 13, 24; then retval = 10 + 16 + 24 = 50. Prints "50".

  8. Complete printed sequence: 3 8 16 13 24 50 — this is option (C).

KEY IDEA

Each call to foo(p) first recurses into both children (left, then right) and only after both have returned does it compute retval = p->val + foo(left) + foo(right) and print it — so this is a post-order traversal, but what gets printed at each node is the sum of the entire subtree rooted there, not the node's own stored value.

WATCH OUT FOR

Assuming the printf prints the node's own value at the moment of visiting it (as in a plain post-order traversal print), giving 3 8 5 13 11 10 (option A) — instead of recognizing that retval accumulates the subtree sum before printing, since the printf statement executes only after both recursive calls have already returned and retval has already been updated.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 9 Recursion questions, with notes

More Recursion questions