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

Step 1: Understand the function behavior
The function foo() computes the sum of all node values in the subtree rooted at p, then prints this sum after recursive calls (postorder traversal). Step 2: Traverse and compute values
- Leaf node (3):
\(\text{retval} = 3 + 0 + 0 = 3\). Prints 3.
- Leaf node (8):
\(\text{retval} = 8 + 0 + 0 = 8\). Prints 8.
- Node (5):
\(\text{retval} = 5 + 3 + 8 = 16\). Prints 16.
- Leaf node (13):
\(\text{retval} = 13 + 0 + 0 = 13\). Prints 13.
- Node (11):
\(\text{retval} = 11 + 0 + 13 = 24\). Prints 24.
- Root (10):
\(\text{retval} = 10 + 16 + 24 = 50\). Prints 50.
Step 3: Final sequence of outputs
The values printed in order: \[ 3, \; 8, \; 16, \; 13, \; 24, \; 50 \] \[ \boxed{3 \; 8 \; 16 \; 13 \; 24 \; 50} \]