GATE CSE 1996 | Question: 4

Question

A binary search tree is used to locate the number $43$. Which of the following probe sequences are possible and which are not? Explain.

$\begin{array}{llllll} \text{(a)}  &  \text{61} & \text{52} & \text{14} &  \text{17} & \text{40} & \text{43} \\
 \text{(b)}  &  \text{2}&  \text{3} & \text{50} &  \text{40} & \text{60} & \text{43} \\
 \text{(c)}  &  \text{10} & \text{65} & \text{31} &  \text{48}&  \text{37} & \text{43} \\
 \text{(d)}  &  \text{81}  &\text{61} & \text{52} &  \text{14} & \text{41} & \text{43} \\
 \text{(e)}  &  \text{17} & \text{77} & \text{27} &  \text{66}&  \text{18} & \text{43}   \end{array}$

Comments

This can be solved using BST property only. Construct BST from the search sequence and remember that you have to move to the next level in a tree after a probe and cannot return to previous levels. Search prove which gives a binary tree which violates BST property (all elements in left subtree are <  and those in right subtree are > than root) will be invalid search sequence.

---

Try this out...

1. All the keys > Search key →  Descending Order
2. All the keys < Search key →  Ascending Order
3. The Search key must be last

If any of these conditions is violated then its not a possible search sequence.

---

So, you will get required explanation from the attachment

Caption

achment

Answer 1

(b) and (e) are not possible.

rest all i/p's will have binary trees with only one child. but (b) and (e) will have two childs at a point. therefore the probe sequence will not be possible.

For better clarification, make BST's for the given i/p's and probe for $43$.

Comments

@ashish if node is having two child and you are visiting the wrong child then how will you revert back from there so no possibilty of getting right answer from that probe sequence  but if it has two child and you have visited the right one then there is no problem and the other case is if it has only one child then you have to go from there only and it can lead to the right probe sequence .

---

Why are u making BST of the given probe sequence? BST already exists and these r the probe sequences. We just have to check if at each value of the given sequence if it is taking correct move(left/right) to search 43 and satisfying the BST property.

---

For b if you draw a BST 60 will be left descendent of 50 at some point which violate property of BST and similarly in option e 18 will be right descendent to 27 which again voilates property of BST.

Answer 2

We have to take each option and check if they are a probable correct search pattern or not. 

This can be done by first assuming that a sequence is correct, and the first element of each option is the root. 

So we imagine and search from the root(the first element of each option) and search all the way till 43. If at any point, the BST property is violated, we stop and declare that that sequence is invalid (not possible) under the BST property for searching for 43.

For eg :- option (B) -> we assume 2 is the root, so since 43 is a larger no. than 2, we would have to go to the right subtree of 2 for searching for 43, and so we do.

We see the next element is 3 in our sequence, so its position is correct since 3 is also greater than 2,

Now we are at node 3, and we have to search for 43, we again go right and since we get 50 which is greater than 3, so its also in its correct position.

We then go to the left of 50 since 43 < 50. Now we get 40 which is also correct since 40 < 50. 

Now we go to the right of 40, since 43 > 40, and we see 60 which is correct but since 60 falls in the left subtree of 50, the BST property is violated. Hence, this sequence is not correct. 

So, after inserting each node in our imaginary BST, we need to check for the BST property overall.

Comments

I think your BST For Option B is Wrong 60 will be the right child of 50 not 40

Also we have to check for probe sequence

---

Answer is correct read carefully @bad_engineer

---

Can you please explain how option(e) is also wrong. I tried it but I didn't find anything wrong with (e).

---

After reaching 18 there is no way to go back. Hence this probe sequence is wrong. 

Answer 3

option b and option e is not possible 

FIRST METHOOD

make the binary search  tree

 binary search tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree

the option a is satisfy all the property

now i am telling one more thing that is why we are doing this ?

from the given the probe sequence , they asked  wether we can search the node 43 through the given sequence 

this thing become more clear after reading option b 

now come to option b

 it means through the given probe sequence we can not reach up to node  43  (because it violate the bst property)

now same thing we can do for the remaining option 

SECOND METHOD (imp and sortcut, here is no need to make bst )

this is the good observation which we can observe after carefully watching the bst

come to option a

in the probe sequence 61 is the root node ,now from 61 we are going to 52 it means we are going in the left subtree of node 61

from these  we can conclude that all the node after the node 61 in the probe sequence should be less then the 61  to satisfy the bst property 

now see all the nodes after the node 61 in the probe sequence are less then 61   means it satisfy our requirement  so move to next node

now come to node 52, from 52 we are going to node 14 ,it means we are going in the  left subtree of node 52 from this we can conclude that  all the node after the 52 should be less then the node 52 , now watch the given sequence ,yes it satisfy now come to the node 14

from the node 14 we are going to the node 17, it means we are going to the right subtree of node 14 so all the node after the node 14 should be greater then the node 14 , now watch the given sequence yes it satisfy 

so now move to node  17 then 40 then 43 same procedure 

key point if we are moving in the left subtree then all the remaining node should be less then that particular node or it we are moving in the right subtree then all the node after that node should be greater then that particular node  (remember these property help in the other example too)

now come to option b 

root node is 2 

from 2 we are moving to 3 it means we are moving in the right subtree from these we concluded that  all the node after this node should be greater then 2 , now watch the given sequence ,yes all are greater then 2  so now move to node 3 

from 3 we are going to 50 , means in the right subtree so all the node after the 3 should be greater then the 3, watch the given sequence ,yes they all are 

so come to node 50 , from 50 we are going to node 40 ,means we are moving  in the left subtree so all the node after the node 50 should be less then the 50 but this is not the case here due to node 60 so this probe sequence is not valid 

same can be done for the remaining option 

Comments

This method is very good but it is not working for sequence 15,33,46,109,94,81,82 when searching for 80 can you clarify this??I mean according to your 2 nd method this sequence is correct but not according to original method ...

---

15,33,46,109,94,81,82,80

Now  when you are moving from 81 to 82 it means you are moving to the right subtree . All remaining element should be greater than 81

But it is not

---

Is  this method is applicable everywhere?

---

Hello Gurdeep Sir! Can you please explain what is the problem with the option (e) I am trying it, but I can't see anything wrong with the (e) but everywhere in answer, (e) option is also mentioned as wrong.

Answer 4

Here we need to concentrate on the term $\text{" probe sequence"}$. It is not saying to draw BST but we have given sequences that should be followed to search the given number. 

So, we should not take this question as we have to create a BST but we need to take sequences as a continuous number(It means we compare the key to the current root only not with global root)

in this way only b and e are not possible

Comments

Try preorder traversal for every sequence after making a bst from them

and then you will know the answer.