in DS
231 views
0 votes
0 votes
A search was performed on some binary search tree. Which of the following is a valid search sequence?

(A) 1, 11, 111, 98, 58, 78, 90, 48, 88
(B) 333, 33, 53, 93, 63, 90, 70, 88
(C) 8, 888, 18, 98, 38, 78, 90, 48, 88
(D) 555, 5, 55, 95, 45, 65, 75, 88
in DS
231 views

4 Comments

(B) is the answer

To search for 88 (Let's say) in all the other options:

(A) 48 is wrongly placed

(C) 48 is wrongly placed

(D) 45 is wrongly placed
1
1
Can you please explain the reason for wrong placement in all cases.

In option (A). After 90 we should go for a number smaller than 90 (if we are searching for 88), therefore we are getting 48, again to get 88 we are going for a number larger than 48. What's wrong here, I'm unable to infer. Please help.

Same is the case with other options as well.
0
0
In option (A), as we are searching for 88, as we have reached 78 we are looking for a number between 79-97 (as 98 is visited before) then we go to 90 & we are now looking for a number between 79-89 then we go to 48 & it is neither equal to our desired key(=88) & nor in the previous search range (78-89) so we exit without reaching to the key.
0
0
I got it now. Thanks a lot for reply. :-)
0
0

1 Answer

0 votes
0 votes

Related questions