GATE IT 2006 | Question: 45

Question

Suppose that we have numbers between $1$ and $100$ in a binary search tree and want to search for the number $55$. Which of the following sequences CANNOT be the sequence of nodes examined?

• A. $\{10, 75, 64, 43, 60, 57, 55\}$
• B. $\{90, 12, 68, 34, 62, 45, 55\}$
• C. $\{9, 85, 47, 68, 43, 57, 55\}$
• D. $\{79, 14, 72, 56, 16, 53, 55\}$

Answer 1

In option C search sequence progress in $...47,68,43,..$

At $47$ we see that search key $55$ is greater and it will be on right side of $47$. so in further comparison a value less than $47$ will not come

Hence, option C is wrong.

Comments

Explanation: Search Key is 55. If Search key < element in sequence then we will consider left subtree and following elements in sequence must be smaller than that element and if search key > element in sequence then we will consider right subtree and following elements must be greater than left subtree. We will iterate till last element in sequence (i.e. till search key is found).

For Example : search 55 and sequence is {10, 75, 64, 43, 60, 57, 55}. 55 > 10 then all elements in sequence following 10 are greater than 10. if yes continue if no then that cannot be sequence of node to be examined and break the loop. Continue loop till last element ie 55. Hope explanation makes sense and understandable.  Hence C is correct ans.

---

in option C first compared  element is 9. that is root. the required item is 55. so in a bst 55 >9 , so will be on the right subtree. now all the comparisons further will be on the right side . and all elements should be greater than 9. now . now next item is 85, it is <55 . so all elements following 85 will be less than 85 and greater than 9. and it will be on left side of 85. Next is 47. and 55 > 47 that means in order to search 55 we need to search in the right sub tree of 47. right sub tree of 47 will contain elements greater than 47 and less than 85( from previous step). we can see there is a 43 in the following sequence. Which is not possible because 43 < 47.

If you progress all the other options in similar logic, you can see that they are all valid.

you can try drawing the corresponding BST also

hope this explanation is ok

---

Thanks sir

Answer 2

Although @Sankaranarayanan P.N ji has provided good and quick way to solve this problem. But still mentioning two more ways to solve this problem. 

(1) In Method 1 we are solving problem via maintaining (Min, Max) window. 

(2) For getting some intuition about method 2. Please refer --> https://cs.stackexchange.com/questions/11043/number-of-possible-search-paths-when-searching-in-bst/11048#11048 .

PS: Much explanation is not added because it will help readers in thinking something  different :)

Answer 3

it is similar to this question https://gateoverflow.in/2756/gate1996-4

Answer 4

all answer looks correct but they have asked  “sequence of nodes examined “ 43 in option C will come out of sequence as the validation fails