GATE CSE 2023 | Question: 37

Question

Consider the $\text{C}$ function $\text{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 $\textsf{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$

Comments

so (p->val) is only there for confusion, and it doesn't traverse in pre-order?

---

why we use here post order

---

@Zgod stack ke top par jo hai ose phle run krenege then output

Answer 1

Given that retval = p → val + foo(p → left) + foo(p → right)

Means it will print the sum of ( value + leftsubtree whole value + right subtree whole value ).

Note that, until the child nodes completes the calculation, parent node calculation step will not complete.

 

Therefore leaf nodes returns the value of leaf nodes alone. ( 3 node, 8 node and 13 node will return 3, 8 and 13 respectively )

5 node will return 5+3+8 = 16

11 node will return 11+13 = 24

10 node will return 10+16+24 = 50

 

So sequence 3,8,16,13,24,50 only possible in the given options

 

As we know, there’s no rule about evaluation order of parameters of ‘+’

possible outcomes : 

1. 3,8,16,13,24,50
2. 8,3,16,13,24,50
3. 13,24,3,8,16,50
4. 13,24,8,3,16,50

Comments

they are evaluating first left subtree then right subtree if we follow right then left then there are also different possible answers

---

First right subtree then left subtree sequences are also included in those 4.

If you are not convinced, let me know which one is missing ?

Please note that 3,13,8,16,24,50 and similar interleaved sequences are not possible.

---

sir i need your help in p n c of discrete maths can u help i am gfetting confused for example when there are 3 item and 10 box
what is the permuattion : i am not getting ineer satisfaction with the asnwers sir can u help me

when item is assigned to box
and when box is assigned to item
can u help me sir

Answer 2

Option C .

Comments

Good one

Answer 3

The function is taking the current node value and calling the function on the left and right child nodes. Recursively, it will reach the leftmost leaf node. The value for the leftmost leaf node is:

retval = 3 + 0 + 0,

and it prints '3'. The value '3' is returned to its parent node.

Now, the value at node '5' is:

retval = 5 + 3 + foo(p->right).

Similarly, foo(p->right) will print and return its value, '8', to the parent node.

Now, retval = 5 + 3 + 8. So, the output '16' is printed and returned to its parent node, '10'. By this time, you should have an intuition of what's happening in the function. This process will continue recursively.

The final output is: 3, 8, 16, 13, 24, 50.

Answer: Option C.

 

 

For tracking purpose,I'm attaching the image

Answer 4

The function is taking the current node value and calling the function on the left and right child nodes. Recursively, it will reach the leftmost leaf node. The value for the leftmost leaf node is:

retval = 3 + 0 + 0,

and it prints '3'. The value '3' is returned to its parent node.

Now, the value at node '5' is:

retval = 5 + 3 + foo(p->right).

Similarly, foo(p->right) will print and return its value, '8', to the parent node.

Now, retval = 5 + 3 + 8. So, the output '16' is printed and returned to its parent node, '10'. By this time, you should have an intuition of what's happening in the function. This process will continue recursively.

The final output is: 3, 8, 16, 13, 24, 50.

Answer: Option C.

Answer 5

basically it's adding the values of left child + right child + root  and doing this process from bottom to top of the tree. just check the final sum i.e 50 and it matches option C. (no need to dry run the whole program )

Answer 6

Anwser is in the uploaded image