<p>We have a sorted list of <span class="math-container">$n$</span> numbers and we shall create a BST for these numbers.</p>
<p>We create a random sequence of zeroes and ones of length <span class="math-container">$n$</span>.</p>
<p>We shall make use of this random binary sequence to form a BST in the following way.</p>
<p>Let's illustrate using an example.</p>
<p>Suppose we have the input to be  <span class="math-container">$[a,b,c,d,e]$</span></p>
<p>&amp; the random binary sequence is <span class="math-container">$[1,0,0,1,0]$</span></p>
<p>Then we form the tree in the following way.</p>
<p>Since <span class="math-container">$a$</span>'s random bit is 1, its successor will be below it in the BST.</p>
<p>Since <span class="math-container">$b$</span>'s random bit is 0, its successor will be above it in the BST.
and so on...</p>
<p><a href="https://i.sstatic.net/hGgNP.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/hGgNP.png" alt="Example" /></a></p>
<p>The random bit of the last value <span class="math-container">$e$</span>, does not matter because it has no successor.</p>
<p>Which gives us the BST as follows
<span class="math-container">$d$</span> is root, its left child is <span class="math-container">$c$</span> and right child is <span class="math-container">$e$</span>.
<span class="math-container">$c$</span> has a left child <span class="math-container">$a$</span> and <span class="math-container">$a$</span> has right child to be <span class="math-container">$b$</span>.</p>
<p>This seems to be random, but I am not convinced.
A random BST should have height to be <span class="math-container">$O(\lg n)$</span>.</p>
<p>But the random binary sequence will have roughly <span class="math-container">$O(n)$</span> zeroes and <span class="math-container">$O(n)$</span> ones with high probability.</p>
<p>Everytime we encounter a zero, the successor of a node lies above the node and so if on average there <span class="math-container">$O(n)$</span> zeroes, the height of the tree on average is also <span class="math-container">$O(n)$</span>.</p>
<p>What is the correct answer?
Does this strategy create a random tree or not?</p>

CC BY-SA 4.0
2021-04-14T20:36:48.027Z
As I understand it the [number of rooted binary trees](https://cs.stackexchange.com/questions/368/counting-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.
Neal Young
CC BY-SA 4.0
2021-04-15T09:29:09.903Z
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.
Vk1
CC BY-SA 4.0
2021-04-15T13:13:28.467Z
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.
Neal Young
CC BY-SA 4.0
2021-04-15T15:38:26.907Z
Thanks for the  clarification. That helped a lot.
Vk1
CC BY-SA 4.0
2021-04-15T17:30:52.277Z
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$.
Neal Young
CC BY-SA 4.0
2021-04-15T17:43:03.577Z
Assuming you resolve this ambiguity somehow, each tree that the process does generate will occur with the same probability, namely $1/2^{n-1}$, because each binary sequence generates a different tree.  (Given the tree, you can reconstruct the binary sequence.)
Neal Young
CC BY-SA 4.0
2021-04-15T17:54:04.870Z
As for the height, if you specify in your definition that, for each 0, the successor will be above the node and _at the root_ (so it becomes the new root), then each such successor will end up on the left spine, so the height of the minimum node ($a$) will be the number of zeroes in the sequence, which w.h.p. (and in expectation) will be about $n/2$.  So then w.h.p. the tree height will be $\Theta(n)$.  (Similarly, if you specify in your definition that, for each 0, the successor is spliced in as the new parent of the node, the length of the right spine will be about $n/2$.)
Neal Young
CC BY-SA 4.0
2021-04-15T18:49:45.417Z
I observed the ambiguity after posting the question, but I was not sure how to resolve the ambiguity, hoping that someone would come up with a slightly better strategy to take a random binary sequence and create a random binary tree.
Vk1
<randomness><binary-trees>
Creating a random tree (BST) on $n$ elements using a random sequence of zeroes and ones
Vk1
# Creating a random tree (BST) on $n$ elements using a random sequence of zeroes and ones

(Asked by: username_0 on 2021-04-14)

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](https://i.sstatic.net/hGgNP.png)](https://i.sstatic.net/hGgNP.png)

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?

**Tags:** randomness, binary-trees

> **Comments:**
> **username_1**: As I understand it the [number of rooted binary trees](https://cs.stackexchange.com/questions/368/counting-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.  
> **username_0**: Ty Prof. username_1 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 username_1.  
> **username_1**: 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.  
> **username_0**: Thanks for the  clarification. That helped a lot.  
> **username_1**: 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$.  
> **username_1**: Assuming you resolve this ambiguity somehow, each tree that the process does generate will occur with the same probability, namely $1/2^{n-1}$, because each binary sequence generates a different tree.  (Given the tree, you can reconstruct the binary sequence.)  
> **username_1**: As for the height, if you specify in your definition that, for each 0, the successor will be above the node and _at the root_ (so it becomes the new root), then each such successor will end up on the left spine, so the height of the minimum node ($a$) will be the number of zeroes in the sequence, which w.h.p. (and in expectation) will be about $n/2$.  So then w.h.p. the tree height will be $\Theta(n)$.  (Similarly, if you specify in your definition that, for each 0, the successor is spliced in as the new parent of the node, the length of the right spine will be about $n/2$.)  
> **username_0**: I observed the ambiguity after posting the question, but I was not sure how to resolve the ambiguity, hoping that someone would come up with a slightly better strategy to take a random binary sequence and create a random binary tree.  

---

## 0 answers

