0
$\begingroup$

We have a sorted list of $n$ numbers and we shall create a BST for these numbers.

We create a random sequence of zeroes and ones of length $n$.

We shall make use of this random binary sequence to form a BST in the following way.

Let's illustrate using an example.

Suppose we have the input to be $[a,b,c,d,e]$

& the random binary sequence is $[1,0,0,1,0]$

Then we form the tree in the following way.

Since $a$'s random bit is 1, its successor will be below it in the BST.

Since $b$'s random bit is 0, its successor will be above it in the BST. and so on...

Example

The random bit of the last value $e$, does not matter because it has no successor.

Which gives us the BST as follows $d$ is root, its left child is $c$ and right child is $e$. $c$ has a left child $a$ and $a$ has right child to be $b$.

This seems to be random, but I am not convinced. A random BST should have height to be $O(\lg n)$.

But the random binary sequence will have roughly $O(n)$ zeroes and $O(n)$ ones with high probability.

Everytime we encounter a zero, the successor of a node lies above the node and so if on average there $O(n)$ zeroes, the height of the tree on average is also $O(n)$.

What is the correct answer? Does this strategy create a random tree or not?

$\endgroup$
8
  • 2
    $\begingroup$ As I understand it the number of rooted binary trees on $n$ nodes is $\frac{1}{n+1}{2n \choose n} \sim \frac{4^n}{\text{poly}(n)}$. But your process can generate only $2^{n-1}$ different trees. So, unless I'm mistaken, there are trees that your process cannot generate, so the answer is no. $\endgroup$ – Neal Young Apr 14 at 20:36
  • $\begingroup$ Ty Prof. Neal Young for taking out the time to answer the question. Quick follow-up question. Out of the universe of $2^{n-1}$ trees, I assumed that the process was generating a random tree. So what you are saying is that just because it cannot create all possible rooted binary trees, the procedure is not random? What am I missing Professor Neal Young. $\endgroup$ – Vk1 Apr 15 at 9:29
  • 2
    $\begingroup$ Well it's clearly a random process, and the tree it generates is random. I assumed that your question was whether it generates a tree uniformly at random, that is, generates every possible tree with the same probability. Per my comment it seems that there must be some trees that it cannot generate at all, that is, that it generates with probability zero, and, if that's the case, it does not generate every possible tree, much less every possible tree with the same probability. $\endgroup$ – Neal Young Apr 15 at 13:13
  • $\begingroup$ Thanks for the clarification. That helped a lot. $\endgroup$ – Vk1 Apr 15 at 15:38
  • $\begingroup$ BTW there's an ambiguity in your definition. E.g. for the bit sequence "0 1 -" for nodes $a, b, c$, there are at least two trees that satisfy your description: the tree with $c$ at the root, with left child $a$, whose right child is $b$, or the tree with $a$ at the root, with right child $c$, whose left child is $b$. $\endgroup$ – Neal Young Apr 15 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.