# Randomized algorithm to make a Binary Search Tree from an array of $n$ distinct elements

An array $\mathcal{A}$ of $n$ distinct integers $\{a_1,a_2,\ldots,a_n\}$ is given. I'm asked to design a randomized (esp. Las Vegas) algorithm to make a Binary Search Tree out of these elements, such that the height of the tree is $\lceil \log{_{2-\epsilon}n}\rceil$, where $\epsilon=\frac{2}{9}$.

If we had to make a perfectly balanced binary search tree, we need to choose the median of the $n$ elements as root in every recursive call. But the height is not exactly $\lceil \log{_{2}n}\rceil$; there is a relaxation by $\epsilon$. So instead of choosing the median we need to choose any value (randomly) from the middle $x\%$ of the sorted version of $\mathcal{A}$. For example, suppose$\mathcal{A}=\{4,2,3,6,1,5,7,10,9,8\}$, $\therefore\mathcal{A_{sorted}}=\{1,2,3,4,5,6,7,8,9,10\}$. Now because the height is not exactly $\lceil\lg n\rceil$, so instead of choosing the median, we need to choose one element randomly from the middle $30\%$ of the elements (say for example), $i.e$ one element randomly from $\{4,5,6\}$. Here this value $30\%(x\%)$ will depend on $\epsilon\ (\frac{2}{9})$. My question is how to derive this $x\%$ from the height information given $i.e$ $\lceil\log{_{2-\epsilon}n}\rceil$ ? $$\lceil\log{_{2-\epsilon}n}\rceil = \left\lceil\frac{\log{_{2}n}}{\log{_{2}{(2-\epsilon)}}}\right\rceil=\left\lceil\frac{\log{_{2}n}}{0.83}\right\rceil$$

I don't need a full explanation, any hint would suffice.

• OK, great, now your question is clearer. That's a good improvement. Thank you. That brings me to the next set of questions: What have you tried? What are your thoughts? Where did you get stuck? We want to help you with your specific problems, not solve your exercise for you. As it is we don't know what this problem is and thus how to help. See here for a relevant discussion. – D.W. Sep 17 '14 at 16:11
• @D.W. Sorry for replying late. I was in the middle of my semester exam. What I've tried is as follows: $$\lceil\log{_{2-\epsilon}n}\rceil = \left\lceil\frac{\log{_{2}n}}{\log{_{2}{(2-\epsilon)}}}\right\rceil=\left\lceil{\frac{\log{_{2}n}}{0.83}}\right\rceil=1.2\left\lceil\log_2n\right\rceil$$ So, it'll create a lop-sided tree with one branch $(1.2-1)\times100=20\%$ higher than the ideal height $i.e\ \log_2n$. Here is where I'm stuck. Does this $20\%$ signify that I've to choose the root element from the middle $20\%$ of the elements of $\mathcal{A}$ ? – dibyendu Sep 23 '14 at 5:29