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