### SET 1

Question 1

**Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?**

1. 3, 5, 7, 8, 15, 19, 25

2. 5, 8, 9, 12, 10, 15, 25

3. 2, 7, 10, 8, 14, 16, 20

4. 4, 6, 7, 9, 18, 20, 25

A : 1 and 4 only

B : 2 and 3 only

C : 2 and 4 only

D : 2 only

Answer Discuss it!

.

Correct answer is :A

Solution :

Inorder traversal of binary search tree gives ascending orders.

Question 2

**The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are**

A : 63 and 6, respectively

B : 63 and 5, respectively

C : 32 and 6, respectively

D : 31 and 5, respectively

Answer Discuss it!

.

Correct answer is :A

Solution :

Maximum no. of nodes in a binary tree with height h 1 h = 2^{h+1}-1 = 64-1 63.

Minimum no. of nodes with height h is h+1(in every only one node will be there). h=5

Question 3

**Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.**

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

A : 40, 30, 20, 10, 15, 16, 17, 8, 4, 35

B : 40, 35, 20, 10, 30, 16, 17, 8, 4, 15

C : 40, 30, 20, 10, 35, 16, 17, 8, 4, 15

D : 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Answer Discuss it!

.

Correct answer is :B

Question 4

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

Answer Discuss it!

.

Correct answer is :19

Solution :

Let the number of vertices of a binary tree with „p? leaves be n then the tree has

(i) p vertices (i.e., leaves) of degree 1

(ii) one vertex (i.e.., root of T) of degree 2

(iii) 'n - p -1' (i.e., interval) vertices of degree 3

(iv) n -1edges

By Handshaking theorem,

p*1+1*2+(n-p-1)*3=2(n-1)

=> n=2p-1

=39 as p=20

n-p=19 vertices have exactly two children

Question 5

**Consider a complete binary tree where the left and the right subtrees of the root are maxheaps. The lower bound for the number of operations to convert the tree to a heap is**

A : Ω (log n)

B : Ω (n)

C : Ω (n log n)

D : Ω (n ^{2})

Answer Discuss it!

.

Correct answer is :A

Question 6

**Consider the following array of elements.**

<89,19,50,17,12,15,2,5,7,11,6,9,100>

The minimum number of interchanges needed to convert it into a max-heap is

A : 4

B : 5

C : 2

D : 3

Answer Discuss it!

.

Correct answer is :D

Solution :

1st swap is : 100 and 15

2nd swap is : 100 and 50

3rd swap is : 100 and 89

Question 7

**While inserting the elements 71,65,84,69,67,83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is**

A : 65

B : 67

C : 69

D : 83

Answer Discuss it!

.

Correct answer is :B

Question 8

**The result evaluating the postfix expression 10 5 + 60 6 / *8 - is**

A : 284

B : 213

C : 142

D : 71

Answer Discuss it!

.

Correct answer is :C

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 ____ .**

Answer Discuss it!

.

Correct answer is :199

Solution :

Let the number of leaf nodes of a binary tree with ‘n’ vertices be ‘p’ then the tree has

(i) ‘p’ vertices of degree ‘1’

(ii) one vertex (i.e. root of T) of degree ‘2’.

(iii) 'n - p - 1' vertices of degree ‘3’

(iv) 'n - 1' edges

By Handshaking theorem,

p×1+1× 2 + (n - p - 1)×3 = 2(n - 1)

n=2p-1

=399 as p =200

Number of nodes having exactly two children are n - p i.e., 199

Question 1

1. 3, 5, 7, 8, 15, 19, 25

2. 5, 8, 9, 12, 10, 15, 25

3. 2, 7, 10, 8, 14, 16, 20

4. 4, 6, 7, 9, 18, 20, 25

.

Correct answer is :A

Solution :

Inorder traversal of binary search tree gives ascending orders.

Question 2

.

Correct answer is :A

Solution :

Maximum no. of nodes in a binary tree with height h 1 h = 2

^{h+1}-1 = 64-1 63.

Minimum no. of nodes with height h is h+1(in every only one node will be there). h=5

Question 3

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

.

Correct answer is :B

Question 4

.

Correct answer is :19

Solution :

Let the number of vertices of a binary tree with „p? leaves be n then the tree has

(i) p vertices (i.e., leaves) of degree 1

(ii) one vertex (i.e.., root of T) of degree 2

(iii) 'n - p -1' (i.e., interval) vertices of degree 3

(iv) n -1edges

By Handshaking theorem,

p*1+1*2+(n-p-1)*3=2(n-1)

=> n=2p-1

=39 as p=20

n-p=19 vertices have exactly two children

Question 5

.

Correct answer is :A

Question 6

<89,19,50,17,12,15,2,5,7,11,6,9,100>

The minimum number of interchanges needed to convert it into a max-heap is

.

Correct answer is :D

Solution :

1st swap is : 100 and 15

2nd swap is : 100 and 50

3rd swap is : 100 and 89

Question 7

.

Correct answer is :B

Question 8

.

Correct answer is :C

Question 9

.

Correct answer is :199

Solution :

Let the number of leaf nodes of a binary tree with ‘n’ vertices be ‘p’ then the tree has

(i) ‘p’ vertices of degree ‘1’

(ii) one vertex (i.e. root of T) of degree ‘2’.

(iii) 'n - p - 1' vertices of degree ‘3’

(iv) 'n - 1' edges

By Handshaking theorem,

p×1+1× 2 + (n - p - 1)×3 = 2(n - 1)

n=2p-1

=399 as p =200

Number of nodes having exactly two children are n - p i.e., 199