The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+36 votes
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 by Boss (16.3k points)
edited by | 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 ?

4 Answers

+39 votes
Best answer

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 by
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."

 

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

Only III is the valid sequence.

Sequence I is wrong after 285.
by Active (1.2k points)
–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
by Boss (11k points)
+3
I. no need to go from 285 to 376 as 273 is less than 285. Hence, answer is D.
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,309 questions
55,743 answers
192,232 comments
90,504 users