Question 1 |

Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.

The value of |A-B| is _____________

The value of |A-B| is _____________

3 | |

4 | |

1 | |

2 |

Question 1 Explanation:

Question 2 |

The post-order traversal of binary tree is ACEDBHIGF. The pre-order traversal is

A B C D E F G H I | |

F B A D C E G I H | |

F A B C D E G H I | |

A B D C E F G I H |

Question 2 Explanation:

Question 3 |

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ___________ .

2.5 | |

4.25 | |

6.5 | |

3.75 |

Question 3 Explanation:

Question 4 |

Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence?

Preorder, postorder | |

Postorder, inorder | |

Postorder, preorder | |

None of these |

Question 4 Explanation:

Question 5 |

The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.

4 | |

5 | |

3 | |

6 |

Question 5 Explanation:

Question 6 |

If the post order traversal gives ab -cd * + then the label of the nodes 1,2,3.. will be

+ , -, *, a,b,c,d | |

a, -,b,+,c,*,d | |

a,b,c,d,-,*,+ | |

-,a,b,+,*,c,d |

Question 6 Explanation:

Question 7 |

A complete binary tree with n non-leaf nodes contains

\log_{2}n nodes | |

n+1 nodes | |

2n nodes | |

2n+1 nodes |

Question 7 Explanation:

Question 8 |

Consider the following New-order strategy for traversing a binary tree:

Visit the root;

Visit the right sub tree using New-order;

Visit the left sub tree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression

3 4 * 5 - 2 ^ 6 7 * 1 + - is given by:

Visit the root;

Visit the right sub tree using New-order;

Visit the left sub tree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression

3 4 * 5 - 2 ^ 6 7 * 1 + - is given by:

+ -167*2^5-34* | |

- +1*67^2-5*34 | |

- +1*76^2-5*43 | |

1 76*+2543*-^- |

Question 8 Explanation:

Question 9 |

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________.

99 | |

100 | |

199 | |

149 |

Question 9 Explanation:

Question 10 |

A binary tree T has 20 leaves. The number of nodes in T having two children is _______.

20 | |

19 | |

39 | |

9 |

Question 10 Explanation:

There are 10 questions to complete.

In Question no 8.

Sir please correct option no C)

to

-+1*76^2-5*43

Thank You Abhishek Chavle,

We have updated the answer.

Question no 47

Options A , C , D are correct

Thank You Abhishek Chavle,

We have updated the answer.