1. Suppose that we create a binary tree on n items by inserting the
items one at a time, with each permutation of the items equally likely,
and each new item inserted at a leaf of the tree. Are all distinct
binary trees equally likely to be generated by this process? Why or why
not?

2. (CLRS 13.2-4): Show that any arbitrary n-node binary search tree can
be transformed into any other arbitrary n-node binary search tree using
O(n) rotations. (Hint: first show that at most n-1 right rotations
suffice to transform the tree into a right-going chain.)

3. (CLRS 14.1-7): Find an O(n log n) time algorithm that takes as input
a sequence of numbers and outputs the number of pairs x,y such that x<y
and x occurs before y in the sequence, using binary search trees
augmented with the number of descendants of each node.

4. (CLRS 14.3-6): Suppose we wish to maintain a set of numbers, subject
to insertion and deletion operations; after each operation we wish to
know the distance between the closest two numbers in the set. Describe
how to do this using only a binary search tree with a constant amount of
additional information at each tree, in logarithmic time per operation.