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...
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?