Question

Consider the C function foo and the binary tree shown. When foo is called with a pointer to the root node of the given binary tree, what will it print?

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;
    }
}

Binary tree structure:

• A. 3 8 5 13 11 10
• B. 3 5 8 10 11 13
• C. 3 8 16 13 24 50
• D. 3 16 8 50 24 13

Hint:

When recursive functions both compute} and print}, carefully check the order of recursion. Here, printing happens after recursion, so it follows a postorder traversal pattern.

Answer 1

The Correct Option is C

The function foo is a recursive function that computes the sum of all nodes in a subtree and prints the sum for each subtree in a postorder traversal (left, right, root). Let's break down how this would work on the given binary tree.

1. Node 3:
   • Both left and right children are NULL, so foo(p→left) and foo(p→right) return 0.
   • retval = 3 + 0 + 0 = 3 is printed.
2. Node 8:
   • Both left and right children are NULL, so foo(p→left) and foo(p→right) return 0.
   • retval = 8 + 0 + 0 = 8 is printed.
3. Node 5:
   • Left child (3) and right child (8) sums have been calculated as 3 and 8 respectively.
   • retval = 5 + 3 + 8 = 16 is printed.
4. Node 13:
   • Both left and right children are NULL, so foo(p→left) and foo(p→right) return 0.
   • retval = 13 + 0 + 0 = 13 is printed.
5. Node 11:
   • Left child is NULL, right child (13) sum is 13.
   • retval = 11 + 0 + 13 = 24 is printed.
6. Root Node 10:
   • Left child (5) sum is 16, right child (11) sum is 24.
   • retval = 10 + 16 + 24 = 50 is printed.

Thus, the sequence of values printed will be 3 8 16 13 24 50. Therefore, the correct option is the third one: 3 8 16 13 24 50.