edited by
14,453 views
55 votes
55 votes

A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys.

  1. $81, 537, 102, 439, 285, 376, 305$
  2. $52, 97, 121, 195, 242, 381, 472$
  3. $142, 248, 520, 386, 345, 270, 307$
  4. $550, 149, 507, 395, 463, 402, 270$

Suppose the BST has been unsuccessfully searched for key $273$. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

  1. II and III only
  2. I and III only
  3. III and IV only
  4. III only
edited by

4 Answers

Best answer
63 votes
63 votes

The option is D.

Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

The question goes like this. IF there had been $\mathbf{273}$  in the actual sequence then which of the following search sequences would have been successful.

In sequence $1$ no need to go from $285$ to $376$ as $273$ is less than $285$.

In sequence $2$ no need to go from $381$ to $472$ as $273$ is less than $381$.

In sequence $4$ no need to go from $395$ to $463$ as $273$ is less than $395$.

In sequence $3$ number $273$ might have been to the left of $307$ and search would have been successful.

Hence, Option D

edited by
29 votes
29 votes
Answer: D

I. no need to go from 285 to 376 as 273 is less than 285.

II. no need to go from 381 to 472 as 273 is less than 381.

IV. no need to go from 395 to 463 as 273 is less than 395.
2 votes
2 votes
Answer is D.

Only III is the valid sequence.

Sequence I is wrong after 285.
–5 votes
–5 votes
In case 2 after 242 no need to go to 381 no need to go to 472 bcos 273 is less than 381

In case 4 after 395 no need to traverse 463 bcos 273 is less than 395

other cases are fine

hence answer is B
Answer:

Related questions

32 votes
32 votes
2 answers
1
Ishrat Jahan asked Oct 29, 2014
12,444 views
How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$