### SET 6

Question 1

**Postorder traversal of a given binary search tree T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?**

A : 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

B : 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

C : 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95

D : 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Answer Discuss it!

.

Correct answer is :A

Solution :

Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.

Question 2

**A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:**

A : 10, 8, 7, 5, 3, 2, 1

B : 10, 8, 7, 2, 3, 1, 5

C : 10, 8, 7, 1, 2, 3, 5

D : 10, 8, 7, 3, 2, 1, 5

Answer Discuss it!

.

Correct answer is :D

Solution :

Original Max-Heap is:

10
/ \
8 5
/ \
3 2

After Insertion of 1.

10
/ \
8 5
/ \ /
3 2 1

After Insertion of 7.

10
/ \
8 7
/ \ / \
3 2 1 5

Question 3

**How many distinct binary search trees can be created out of 4 distinct keys?**

A : 5

B : 14

C : 24

D : 42

Answer Discuss it!

.

Correct answer is :B

Question 4

**In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is A**

A : nk

B : (n - 1)k + 1

C : n(k - 1) + 1

D : n(k - 1)

Answer Discuss it!

.

Correct answer is :C

Solution :

We can easily verify the above relation by taking some example binary trees.

Question 5

**In a binary max heap containing n numbers, the smallest element can be found in time**

A : O(n)

B : O(log n)

C : O(loglogn)

D : O(1)

Answer Discuss it!

.

Correct answer is :A

Solution :

In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)

Question 6

**A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.**

A : log 2n

B : n

C : 2n + 1

D : 2^{n}-1

Answer Discuss it!

.

Correct answer is :D

Solution :

For a right skewed binary tree, number of nodes will be 2^n – 1. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15

Question 7

**A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?**

A : 1, 3, 5, 6, 8, 9

B : 9, 6, 3, 1, 8, 5

C : 9, 3, 6, 8, 5, 1

D : 9, 5, 6, 8, 3, 1

Answer Discuss it!

.

Correct answer is :D

Solution :

Following 3-ary Max Heap can be constructed from sequence given option (D)

9
/ |
/ |
5 6 8
/ |
/ |
3 1

Question 8

**A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?**

A : 10, 7, 9, 8, 3, 1, 5, 2, 6, 4

B : 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

C : 10, 9, 4, 5, 7, 6, 8, 2, 1, 3

D : 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Answer Discuss it!

.

Correct answer is :A

Solution :

After insertion of 7

9
/ |
/ |
7 6 8
/ |
/ |
3 1 5

After insertion of 2

9
/ |

Question 1

.

Correct answer is :A

Solution :

Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.

Question 2

.

Correct answer is :D

Solution :

Original Max-Heap is:

10 / \ 8 5 / \ 3 2After Insertion of 1.

10 / \ 8 5 / \ / 3 2 1After Insertion of 7.

10 / \ 8 7 / \ / \ 3 2 1 5

Question 3

.

Correct answer is :B

Question 4

.

Correct answer is :C

Solution :

We can easily verify the above relation by taking some example binary trees.

Question 5

.

Correct answer is :A

Solution :

In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)

Question 6

.

Correct answer is :D

Solution :

For a right skewed binary tree, number of nodes will be 2^n – 1. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15

Question 7

.

Correct answer is :D

Solution :

Following 3-ary Max Heap can be constructed from sequence given option (D)

9 / | / | 5 6 8 / | / | 3 1

Question 8

.

Correct answer is :A

Solution :

After insertion of 7

9 / | / | 7 6 8 / | / | 3 1 5After insertion of 2

9 / |