Discussion
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-\(\gt\)val + foo(p-\(\gt\)left) + foo(p-\(\gt\)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?
Answer: C
The program prints 3 8 16 13 24 50.
foo computes the sum of the values in the subtree rooted at p, and it prints that sum only after both recursive calls have returned, so the subtrees are printed in post-order: left subtree, right subtree, then the node.
- Node 3: prints 3. Node 8: prints 8.
- Node 5: 5 + 3 + 8 = 16, printed.
- Node 13: prints 13. Node 11: 11 + 0 + 13 = 24, printed.
- Root 10: 10 + 16 + 24 = 50, printed.
'3 8 5 13 11 10' is the post-order of the node values, which would print val rather than the subtree sums. '3 5 8 10 11 13' is the in-order sequence. '3 16 8 50 24 13' has the right sums but in an in-order arrangement that the code does not produce.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development