Question

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70, 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?

• A. 50
• B. 128
• C. 64
• D. 35

Answer 1

The correct option is D 35

In Binary Search Tree to traverse each node, while searching for any key only order of left elements of key and right element of key is matter ie. 10, 20, 40, 50, [key], 90, 80, 70 because we need to search element 60. So order of elements less than 60 will be only 10, 20, 40, 50 and order of elements greater than 60 will be 90, 80, 70.

So number of ways are = Arrangement of 7 numbers such that 4 element order same and remaining 3 elements order also same

$=\frac{7!}{3!4!}=35$