Randomly constructed binary search tree $(30$ pts $)$ Everybody hates rotations. So it would be nice to be able to insert new elements into a binary search tree $($BST$)$ without the need for rotations. But we know that a BST can have depth $\backslash$Omega $($n$)$ after n insertions if we don't do rotations. Again, randomization comes to the rescue, and it turns out that we can simply insert the n keys in a random order without doing any rotation. The figure below shows an example, where each node is associated with two numbers. The first number is the order number while the second number is the key. In the following, we simply refer to the i$-$th node inserted as "node i $".($a$)$ Consider a set of