Consider an example:

k = 2(internal nodes)

leaves = 2k + 1 = 2 × 3 - 1 = 5

satisfies the case

Tips and Tricks:

If n- ary tree with k internal nodes, then number of leaves:

L = (n – 1) × k + 1

L = (3 – 1) k + 1

Node:

n, m points to 100

(char *)n = 100

'a' + 5 = f

∴ *(100) = f

(char *)n + 2 = 102

'c' + 1 = d

∴ *(102) = d

Output: f, d

Before function execution:

After function execution:

*x = 2020, *y = 202

∴ b = 2020

Variable a remained unchanged

Therefore options 1, 3, and 4 are correct.

Data:

number of distinct keys = n = 9

Formula:

Number of binary search trees = $\frac{{}^{2n}{C}_n}{n+1}$

Calculation:

Number of binary search trees = $\frac{{}^{18}{C}_9}{10}$ = 4862

Concept:

Right sub tree of a node contains only nodes with values greater than or equal to the node’s value.

Left sub tree of a node contains only nodes with values less than the node’s value.

Explanation:

B1:

B2:

Right most element of B1 is 5 and Left most element of B2 is 1, difference between these values is 4.

Option 3 is the correct answer.

Output = MUL( MUL(a + 1, b), POW(b + 1)) )

              = MUL( (a + 1*b), (b + 1*b + 1) )

              = ( a + 1 * b * b + 1 * b + 1  )

              = 3 + 1 * 2 * 2 + 1 * 2 + 1

              = 3 + 4 + 2 + 1

              = 10

Confusion: 

This is the most confusing question if you don’t know about Macros and Preprocessors. 

If question defines the function as –

• #define MUL(a,b) (a)*(b)
• #define POW(a) (a)*(a)

Then it will give –

Output= ( ((a + 1) * b) * ((b + 1) * (b + 1))  )

              = ((3 + 1) * 2) * ((2 + 1) * (2 + 1))

              = 4 * 2 *3 * 3

              = 72 { Wrong output for given question}

Hence, the correct answer is 10.

Output is the frequency of each%attendance above 25.

int result [75] //  

To store frequencies of ages above 25. We can ignore ages below 25 so take an array of 75 numbers where a[0] corresponds to 26, a[1] corresponds to 27, …, a[74].

Hence An array of 75 integers is enough.

Concept :

• (char*)&y meaning: Points to only 8 bits of y( From LSB ).
• Binary of x

• Value of  y = Complement  of all bits of x

• Binary of y 

• Decimal value of this binary is - 2 or *p = - 2

Hence option 4 is the correct answer. 

Graph with minimum height:

Graph with maximum height:

Tips and Tricks:

If n is number of nodes and h is minimum height of in a binary search tree, then

2^h+1 – 1 = n

2^h+1 – 1 = 63

2^h+1 = 64

2^h+1 = 2⁵⁺¹

∴ h = 5

If n is number of nodes and H is maximum height of in a binary search tree, then

H = n – 1

H = 63 -1

Enqueue:

While 1st  stack is not empty, push everything from 1st to 2nd stack.

Push an element to 1st stack.

Push everything back to 1st stack.

Here time complexity will be O(n)

Dequeue:

while 1st stack is not empty then Pop an item from stack1 and return it

Here time complexity will be O(1)

Therefore option 1 and 3 are correct.

Initially S is empty,

∴ f(s) = 0

f(push(S, 2)) = 2

f(push(S, -3)) = max (2, 0) – 3 = -1

f(push (S, 2)) = max (-1, 0) + 2 = 2

f(push (S, -1)) = max (2, 0) – 1= 1

switch('2')

control will come to case '2'

since case '2': doesn't have break statement to will go to case '3'

In case '3': Java program, is printed

since case '3': doesn't have break statement to will go to case '4'

From case '4' to it will to case '5' break will execute and the switch will terminate.

Output: Java program,

Preorder Traversal: ABDGEHJIKCF

Inorder Traversal: DGBJHEIKACF

Postorder Traversal: GDJHKIEBFCA

Option 2:

(PRE (B), POST (I), IN (D)) = (2, 6, 1) gives the correct order.

Concept:
The breadth-first search algorithm uses a queue data structure while the depth-first search algorithm uses a stack data structure in its implementation.

The necessary condition to detect if a circular queue of capacity (n-1) is full is (rear+1) mod n = front 

The time complexity of converting a fully parenthesized infix expression to postfix expression is O(n), that is, traverse the equation

Conclusion:

Options1, 2 and 4 are correct

Tree Method

Here, sum of (numbers in square box) & (no. of time(pf)) will give total no. of times GATE2021 printed i.e, 22 Times.

NOTE: 

Always use TREE method to solve multiple recursive call Questions.

The above program can be understand by taking a simple example of 5 nodes Linked list.

The above program deletes every even number node in the linked list (in above example - second, fourth, … so on node will be deleted.

Option 1: 20, 18, 5, 8, 13, 9, 10, 12

It is a valid traversal.

Option 2:  30, 28, 15, 10, 13,12, 11, 9

Since 9 is less than 10 and to the right of it. Therefore it is not a valid traversal sequence of the binary search tree

Option 3: 10 30 40 33 39 37 38, 34

Since 34 is less than 37 and to the right of it. Therefore it is not a valid traversal sequence of the binary search tree

Option 4: 40, 50, 60, 55, 58, 56, 57,59

Since 59 is greater than 58 and to the left of it. Therefore it is not a valid traversal sequence of the binary search tree

Output is 15

Statement I: TRUE

number of nodes = n = 3

Maximum height = n - 1 = 2

Statement II: TRUE

A binary tree can be constructed uniquely if

1. preorder and inorder traversal is given

2. postorder and inorder is given

But given tree is binary search tree, inorder traversal of the binary s.earch tree is sorted and postorder traversal is given. Hence tree can be constructed uniquely.

Statement III: TRUE

If height of root node is 0, then the maximum height of nodes in binary tree of height h is 2h+1 – 1.

Take N = 32

Output will be same for 65 and 66 as well.

For N = 32 it will print '5'

For N = 65 it will print '5'

For N = 66 it will print '5'

Hence, the sum of smallest three values of N = 32 + 65 + 66 = 163

Binary Search Tree:

INORDER: 14, 15, 18, 20, 22, 23, 25, 30

Traversal time complexity = O(n)

Store the element in an array in reverse order

Filling the array in reverse order. Time complexity = Θ(n)

Total time complexity = Θ(n) + Θ(n) = Θ(n)

Max-heap:

• Smallest element (12) of the max heap is always at the leaf.
• Second largest element (25) in a max heap is always a child of the root node

MAX heap:

Option 2, 3 and 4 are true 

Important Points:

A binary search tree can be constructed from a max heap in Θ(n2) time

Assume that distinct elements are present

Insert 15 at the leaf node of above given tree.

Swap 15 with 27 to satisfy min heap property

Concept:

The given question is an example of triple-order traversal i.e. data of each node is printed thrice. To solve such questions, we assign a number to each line which is a part of recursion and write those numbers along with the nodes of the given tree. Then the tree is traversed in top to down, left to right manner and the corresponding action is performed according to the number assigned.

Solution:

The code fragment is assigned numbers as given below:

traversal(t)

{

    if(t)

    {

          1. print(t → data);

          2. traversal(t → left);

          3. print(t → data);

          4. traversal(t → right);

          5. printf(t → data);

    }

}

These numbers are written along with the nodes of the tree as given below:

The tree is traversed from top to down and left to right i.e. the traversal starts from the node A, moves downwards to node E, then again move upwards to node A and then move downwards towards node H.

The actions are performed accordingly. For example, if node C is picked, the action will be performed as: firstly the data in node i.e. 'C' will be printed. Then the function traversal(t → left) will be called and the data of the node i.e. 'F' will be printed. Again the function traversal(t → left) will be called which will return NULL and the action corresponding to line 3 i.e. to print the data (F)will be performed. Now 'E' will be printed again. Similarly, traversal(t → right) will be called which will return NULL  and the action corresponding to line 4 i.e. to print the data (F) will be performed. 

Likewise,​ the actions will be performed on each node and the output will be ABDDEEEDBBACFFFCGGHHHGCA.

4 2 5 ^ * 14 7 / - 7 5 * +

Push: 9, 2 and 5

Pop: 2 and 5

Perform operation: 2 ^ 5 = 32

Push: 32

Pop: 32 and 4

Perform operation: 4 × 32 = 128

Push: 128

Also push: 14 and 7

Pop: 7 and 14

Perform operation: 14 ÷ 7 = 2

Push: 2

Pop: 128 and 2

Perform operation: 128 - 2 = 126

Push: 126

Also push: 7 and 5

Pop: 5 and 7

Perform operation: 7 × 5 = 35

Push: 35

Pop: 35 and 126

Perform operation: 126 + 35 = 161

Push: 161

After evaluating: 161 is present onto the stack

Initially count = 0

Output of the code is 27.

Important Points:

Initialization statement is executed only once.

Incremental statement is executed at the end of every iteration