Register

Suppose we have numbers between 1 and 1000 in a binary search tree and we are searching for 360. Which of the following sequence could not be sequence of nodes examined?

5,531 views
2 votes
2 votes
1.  2, 252, 401, 398, 330, 344, 350, 360

2.  924, 220, 911, 244, 898, 258, 362, 360

3.  925, 202, 911, 240, 950, 245, 360

4.  2, 399, 387, 219, 266, 382, 381, 278, 360
User Avatar

1 Answer

Best answer
9 votes
9 votes

In binary search after each comparison 

  1. if value > x, the numbers greater than x are avoided
  2. if value < x, the numbers lower than x are avoided

These avoided numbers won't come again in any comparison. 

If we see the 3rd sequence given. 911 > 360 and after this 950 came. So, this is an invalid sequence. 

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
3
dhruba asked Jun 5, 2023
1,151 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). How many comparisons are needed in the worst case scenario to determine that the key is not in the array?
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
User Avatar
Link Copied!