Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation EXTRACT-MAX(A) extracts and deletes the maximum element from A. The operation INSERT(A, key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
Consider the C function foo and the binary tree shown.
![GATE CSE 2023 Data Structures - Trees Question 3 English](https://app-content.cdn.examgoal.net/fly/@width/image/jaoe38c1lyr4baio/72d79ddd-40f1-433a-a253-f51a1839d92e/00eae000-44ef-11ef-ba4e-05f55505d0da/file-jaoe38c1lyr4baip.png?format=png)
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?
Consider the following statements.
S1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2 : The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
Which one of the following options is correct?