Consider the C function foo and the binary tree shown. typedef struct node {…
2023
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?
- 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
Attempted by 152 students.
Show answer & explanation
Correct answer: C
Key insight: foo performs a postorder traversal and at each node computes and prints the sum of that node's value plus the sums of its left and right subtrees.
Visit node 3 (leaf): retval = 3. Printed: 3
Visit node 8 (leaf): retval = 8. Printed: 8
Visit node 5: retval = 5 + 3 + 8 = 16. Printed: 16
Visit node 13 (leaf): retval = 13. Printed: 13
Visit node 11: retval = 11 + 13 = 24. Printed: 24
Visit root node 10: retval = 10 + 16 + 24 = 50. Printed: 50
Therefore the sequence printed by foo when called on the root is: 3 8 16 13 24 50