AOA ASSINGMENT#2

Group members

NAME: Roll Numbers

Muntahir ali BCSM-S16-020

Faran Ahmad BCSM-S16-001

Mubeen Ahmed BCSM-S16-021

?

Q: Suppose that we have numbers between 1 and 1000 in a binary search tree, and we

want to search for the number 363. Which of the following sequences could not be

the sequence of nodes examined?

a. 2, 252, 401, 398, 330, 344, 397, 363.

b. 924, 220, 911, 244, 898, 258, 362, 363.

c. 925, 202, 911, 240, 912, 245, 363.

d. 2, 399, 387, 219, 266, 382, 381, 278, 363.

e. 935, 278, 347, 621, 299, 392, 358, 363.

ANSWER

In this question the part (c) and part (e) is not a sequence of node examined because in part (c) the value of 912 is greater then 911 and in part (e) the value of 347 is greater then 299

Therefore the left side of a child is must be smallest then their root node

Q: Professor Bunyan thinks he has discovered a remarkable property of binary search

trees. Suppose that the search for key k in a binary search tree ends up in a leaf.

Consider three sets: A, the keys to the left of the search path; B, the keys on the

search path; and C, the keys to the right of the search path. Professor Bunyan

claims that any three keys a € A, b € B, and c € C must satisfy a