I came across this question. However, I don't know how to approach this and solve. Any help is appreciated. Thanks
When searching for the key value 30 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 30?
On
We can divide this into two set of values, smaller than $30$ and greater than $30$. $$(\color{blue}{10,20},\color{red}{40,50,70,80,90})$$
The values in blue are smaller than $30$ $\mbox{ }\color{blue}{10,20}$
The values in red are greater than $30$ $\mbox{ }\color{red}{40,50,70,80,90}$
Path to the node $30$ has involved those nodes. So, the possible solution to the given problem is $$\{S,S,S,S,S,L,L\}$$ So, the total number of possible ways $=$ all permutations of that set which is $=\dfrac{7!}{2!\times5!}$
Therefore, different orders are possible in which these key values can occur on the search path from the root to the node containing the value $30$ is $21$
If all the keys are encountered, then the keys $10$ and $20$ have to be in that order, and the keys $90$, $80$, $70$, $50$, $40$ have to be in that order; these two groups can be interleaved in an arbitary way, which allows for $\binom{5+2}2=21$ different orders.
If only some, not necessarily all the keys are encountered, we can choose $0\le k\le2$ of the values $10$, $20$ and $0\le l\le5$ of the values $40$, $50$, $70$, $80$, $90$. Each of the two groups has to be ordered in itself, but the two groups can be interleaved in an arbitrary way. That makes
$$ \sum_{k=0}^2\sum_{l=0}^5\binom2k\binom5l\binom{k+l}k=528\;. $$
Here's the Wolfram|Alpha computation.