Dark Mode

18,448 views

47 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}$

$\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}$

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.

2

0

41 votes

Best answer

@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 .

0

6

18 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.

2

0

14 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

0

1

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