3.6k views

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
in DS
edited | 3.6k views
+1
what  we have to  found ..   valid  sequence or  invalid  sequence..?   little  bit confusion..!!!
0
found valid sequence
+2

Although many people have given correct answer. But just mentioning another approach to solve this problem. Refer --> http://cs.stackexchange.com/questions/11043/number-of-possible-search-paths-when-searching-in-bst/11048#11048

Break the list and two parts and verify.

0
@chhotu ,can you implement ?

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

by Boss (21.3k points)
edited
0
well explained!
+1

Suppose the BST has been unsuccessfully searched for key 273

It is like saying as "IF there had been 273  in the actual sequence then which of the following search sequences would have been unsuccessful."

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.
by Boss (33.8k points)
0
why pls explain?pls explain elaborately why option 3 is correct?
+1 vote

Only III is the valid sequence.

Sequence I is wrong after 285.
by Active (1.2k points)
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

by Boss (11k points)
+3
I. no need to go from 285 to 376 as 273 is less than 285. Hence, answer is D.

1
2