edited by
22,702 views
54 votes
54 votes
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}$
edited by

7 Answers

Best answer
44 votes
44 votes

(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$.

edited by
19 votes
19 votes

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.

17 votes
17 votes

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 

edited by
5 votes
5 votes

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

edited by

Related questions

26 votes
26 votes
5 answers
1
Kathleen asked Oct 9, 2014
30,451 views
A binary search tree is generated by inserting in order the following integers:$$50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24$$The number of nodes in the left subtree and ...
24 votes
24 votes
4 answers
2
29 votes
29 votes
3 answers
3
Kathleen asked Oct 9, 2014
12,122 views
In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?$1$$3$$7$$8$
39 votes
39 votes
6 answers
4
Kathleen asked Oct 9, 2014
13,622 views
An advantage of chained hash table (external hashing) over the open addressing scheme isWorst case complexity of search operations is lessSpace used is lessDeletion is ea...