Number of possible search paths when searching in BST

Question

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$

1. Is this a correct answer?

2. If not, whats the better approach?

3. I would like to generalize. If $n$ nodes are given then total possible search paths would be $2^{n-1}$

Answer 1

If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order.

Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller numbers are) and we never meet numbers larger than $K$. Hence the numbers 90, 80, 70 must occur along the search in that order.

The sequences 10, 20, 30, 40, 50 and 90, 80, 70 can then be shuffled together, as long as their subsequences keep intact. Thus we can have 10, 20, 40, 50, 90, 80, 70, but also 10, 20, 90, 30, 40, 80, 70, 50.

We now can compute the number, choosing the position of large and small numbers. See the comment by Aryabhata. We have two sequences of 4 and 3 numbers. How many ways can I shuffle them? In the final 7 positions I have to choose 3 positions for the larger numbers (and the remaining 4 for the smaller numbers). I can choose these in $7 \choose 3$ ways. After fixing these positions we know the full sequence. E.g., my first example has positions S S S S L L L the second has S S L S L L S.

You ask for a generalization. Always the $x$ numbers less than the number found, and the $y$ numbers larger are fixed in their relative order. The smaller numbers must go up, the arger numbers must go down. The number is then $x+y \choose y$.

PS (edited). Thanks to Gilles, who noted that 30 is not in the question.

Answer 2

We will convert Moves to Text. It is given that During Search we have Traversed these nodes

as it can be seen that Red ones are bigger than 60 and blue ones are smaller than 60.

Path to node 60 has involved those nodes. So, one of the possible solution to the problem is $$\{S,S,S,S,L,L,L\}$$ any other solution will contains these moves only. coz at a time on a node we can get directions as S or L on comparison and since its given that those nodes were encountered it means directions were picked from that set.

Hence, total number of possible solutions = all Permutations of that set, which is given by $$\frac{7!}{4! \times 3!} = 35$$ answer = option A