# Answer to Question #18065 in Quantitative Methods for Sujata Roy

Question #18065

Which of the following can be the

sequence of nodes examined in

binary search tree while searching

for key 88 ?

(A) 90, 40, 65, 50, 88

(B) 90, 110, 80, 85, 88

(C) 190, 60, 90, 85, 88

(D) 65, 140, 80, 70, 88

sequence of nodes examined in

binary search tree while searching

for key 88 ?

(A) 90, 40, 65, 50, 88

(B) 90, 110, 80, 85, 88

(C) 190, 60, 90, 85, 88

(D) 65, 140, 80, 70, 88

Expert's answer

Ans:-C

Explanation:- In order to find a solution for a question like above, given the data draw a binary search tree for each one of the options. The first item is the root. Any value less than the root will form the left side of the tree and any value greater than the root will form the right side of the tree. When you draw such a tree, if you find no node has a left and right child then such a sequence would be valid. If you find that the tree has a left and right child for any node then that sequence is invalid. If you draw the tree for all the 4 options given in the question you will find that only option C does not have left and right child for any node. So option C is correct.

Explanation:- In order to find a solution for a question like above, given the data draw a binary search tree for each one of the options. The first item is the root. Any value less than the root will form the left side of the tree and any value greater than the root will form the right side of the tree. When you draw such a tree, if you find no node has a left and right child then such a sequence would be valid. If you find that the tree has a left and right child for any node then that sequence is invalid. If you draw the tree for all the 4 options given in the question you will find that only option C does not have left and right child for any node. So option C is correct.

## Comments

## Leave a comment