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
