Nombre de chemins de recherche possibles lors de la recherche dans BST

J'ai la question suivante, mais je n'ai pas de réponse à cela. J'apprécierais si ma méthode est correcte:

Q. Lors de la recherche de la valeur de clé 60 dans une arborescence de recherche binaire, les nœuds contenant les valeurs de clé 10, 20, 40, 50, 70, 80, 90 sont parcourus, pas nécessairement dans l'ordre indiqué. Combien d'ordres différents sont possibles dans lesquels ces valeurs clés peuvent apparaître sur le chemin de recherche à partir du nœud racine contenant la valeur 60?

(A) 35 (B) 64 (C) 128 (D) 5040

D'après la question, je comprends que tous les nœuds donnés doivent être inclus dans la traversée et finalement nous devons atteindre la clé, 60. Par exemple, une telle combinaison serait:

10, 20, 40, 50, 90, 80, 70, 60.

Puisque nous devons traverser tous les nœuds donnés ci-dessus, nous devons commencer soit par 10 ou 90. Si nous commençons par 20, nous n'atteindrons pas 10 (puisque 60> 20 et nous traverserons le sous-arbre droit de 20)

De même, nous ne pouvons pas commencer par 80, car nous ne pourrons pas atteindre 90, puisque 80> 60, nous traverserons dans le sous-arbre gauche de 80 & n'atteindrons donc pas 90.

Prenons 10. Les nœuds restants sont 20, 40, 50, 70, 80, 90. Le nœud suivant pourrait être 20 ou 90. Nous ne pouvons pas prendre d'autres nœuds pour la même raison mentionnée précédemment.

Si nous considérons de la même manière, à chaque niveau, nous avons deux choix. Puisqu'il y a 7 nœuds, deux choix pour les 6 premiers et aucun choix pour le dernier. Il y a donc totalement

permutations = 2 6 =$2*2*2*2*2*2*1$$2^6$$64$

1. Est-ce une bonne réponse?

2. Sinon, quelle est la meilleure approche?

3. Je voudrais généraliser. Si nœuds sont donnés, le nombre total de chemins de recherche possibles serait de 2 n - $n$$2^{n-1}$

Si vous cherchez la clé 60, nous atteignons un nombre $K$ moins de 60, nous allons à droite (là où sont les plus grands nombres) et nous ne rencontrons jamais de nombres inférieurs à $K$. Cet argument peut être répété, donc les nombres 10, 20, 40, 50 doivent apparaître lors de la recherche dans cet ordre.

De même, si vous recherchez la clé 60, nous atteignons un nombre $K$ supérieur à 60, nous allons à gauche (où se trouvent les plus petits nombres) et nous ne rencontrons jamais de nombres supérieurs à $K$. Par conséquent, les nombres 90, 80, 70 doivent apparaître lors de la recherche dans cet ordre.

Les séquences 10, 20, 30, 40, 50 et 90, 80, 70 peuvent ensuite être mélangées ensemble, tant que leurs sous-séquences restent intactes. On peut ainsi avoir 10, 20, 40, 50, 90, 80, 70, mais aussi 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.

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

Hence, total number of possible solutions = all Permutations of that set, which is given by