edited by
1,019 views
7 votes
7 votes
In a binary search tree, the key with value $5$ was searched after traversing nodes with values $1, 3, 4, 6, 7, 8, 9$ not necessarily in this order. Lets $P$ is the probability that $3rd$ element on the search path begging from root is either $3$ or $8$, and $N$ are the number of different orders possible in which given nodes can be traversed before finding node with value $5$. Find $\frac{N}{10}+P$
edited by

1 Answer

Best answer
10 votes
10 votes

$\begin{align*} &\text{Given that , 5 is found after traversing 1,3,4,6,7,8,9 in some order} \\ &\text{Assume while searching we did not get 1 yet, but somehow arrive at 3 looking for 5} \\ &\text{From 3 we will go right} \Rightarrow \text{That means we will search greater than 3 only} \\ &\text{In this scenario we will never arrive at node 1 } \\ &\text{So, we can conclude that 1 must be visited before 3, and 3 must be visited before 4} \\ &\Rightarrow \text{order of visiting 1,3,4 will not change, it will be always 1,3,4 while searching for 5} \\ &\Rightarrow \text{Similarly , order of visiting 8,7,5,9 will be 9,8,7,6 only in a search for 5} \\ &\Rightarrow \text{So, } \frac{7!}{3!.4!} = 35 \text{ valid orders of numbers } \left \{ 1,3,4,6,7,8,9 \right \} \text{with respect to the question} \\ & \Rightarrow N = 35 \\ \\ &\text{Now,} \\ \end{align*}$

$\begin{align*} &\text{Keeping 3 in 3rd position we have }2*4 = 8 \text{ valid orders} \\ &{\color{red}{\text{ (put 1 two ways and 4 in 4 ways)}}}\\ &\text{Keeping 8 in 3rd position we have }2*\binom{4}{2} = 12 \text{ valid orders} \\ &{\color{red}{\text{ (put 9 two ways and 7,6 in 4C2 ways)}}}\\\\ &\Rightarrow \text{Total 20 valid orders having 3 or 8 in the 3rd position} \\ &\Rightarrow P = \frac{20}{35} \\ &\Rightarrow \frac{N}{10} + P = 3.5 + \frac{20}{35} \\ \end{align*}$



Although the above answer is nicely explained. I am just making an attempt to make it more clear . 

How the above $35$ orders are there ?

$1-3-4 - 9-8-7-6$ : This order must be maintained i.e, $1-3-4$ and other order $9-8-7-6$.

Hence, Total ways : $\frac{7!}{4!*3!} = 35$ ways.


First fix $3$ at the 3rd spot and suppose elements are stored in an array like : 1,9,3,_,_,_,_,5

Now, we have to fill the four places such that order is not violated like :

  • 8,4,7,6
  • 8,7,4,6
  • 8,7,6,4
  • 4,8,7,6

Or using permutations, we can directly say $\frac{4!}{3!*1!}= 4$ ways

We wil get another $4$ ways for this too : 9,1,3,_,_,_,_,5


Now, fix $8$ at the 3rd spot and suppose elements are stored in an array like : 1,9,8,_,_,_,_,5

Now, we have to fill the four places with the remaining elements such that order is not violated like :

  • 3,4,7,6
  • 7,3,6,4
  • 7,6,3,4
  • 3,7,6,4
  • 7,3,4,6
  • 3,7,4,6

Or using permutations, we can directly say $\frac{4!}{2!*2!}= 6$ ways

Again, We wil get another $6$ ways for this too : 9,1,3,_,_,_,_,5


Hence, Total orders which follow the given representation : $4 + 4 + 6 + 6 = 20$ out of $35$.

So, Probability = $\frac{20}{35}$

edited by

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
4