I have the following question, but don't have answer for this. I would appreciate if my method is correct :
Q. 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 node containing the value 60?
(A) 35 (B) 64 (C) 128 (D) 5040
From the question, I understand that all nodes given have to be included in traversal and ultimately we have to reach the key, 60. For example, one such combination would be :
10, 20, 40, 50, 90, 80, 70, 60.
Since we have to traverse all nodes given above, we have to start either with 10 or 90. If we start with 20, we will not reach 10 (since 60 > 20 and we will traverse right subtree of 20)
Similarly, we cannot start with 80, because we will not be able to reach 90, since 80>60, we will traverse in left sub tree of 80 & thus not reaching 90.
Lets take 10. The remaining nodes are 20, 40, 50, 70, 80, 90. Next node could be either 20 or 90. We cannot take other nodes for same earlier mentioned reason.
If we consider similarly, at each level we are having two choices. Since there are 7 nodes, two choices for first 6 & no choice for last one. So there are totally
$2*2*2*2*2*2*1$ permutations = $2^6$ = $64$
Is this a correct answer?
If not, whats the better approach?
I would like to generalize. If $n$ nodes are given then total possible search paths would be $2^{n-1}$