1. x is a leaf node if, among it and its two neighbors, it is the last to be chosen. Therefore, when x is neither the smallest nor the largest element, the probability that it is a leaf is 1/3. When it is the smallest or largest, there is only one neighbor, and the probability that it is a leaf is 1/2.

2. The root can have rank four if it has two children that are both of rank 2. To minimize the number of nodes in the tree, each of the two nodes of rank 2 should have one child of rank 1 (with two external nodes as its children) and one of rank 0 (an external node itself). Thus, the total number of nodes in the tree is 11.

3a. One possible choice is to set w_i = 1/i^2.  Then W = sum(1/i^2) = O(1) (see https://en.wikipedia.org/wiki/Basel_problem) and log(W/w_i)=2 log i = O(log i).
It would also work to use 1/i^c for any constant c > 1. However, using 1/i as the weight does not work, because then we would have W = Theta(log n).

3b. There was a typo in this part: I meant to state that the sorted order by value is the same as the sorted order by frequency, so that the most-frequently accessed item would be leftmost in the tree, etc.

One solution (for the problem as intended) would be to make a sequence
of complete binary trees of size 1, 3, 7, 15, 31, etc
and then make the tree of size 1 be the left child of the root,
the tree of size 3 be the left child of the root's right child,
the tree of size 7 be the left child of the root's rightmost grandchild,
the tree of size 15 be the left child of the root's rightmost great-grandchild,
etc. Stop this process when you have at least n nodes, trimming the last of the complete binary trees arbitrarily to reduce the total number of nodes to exactly n, and then fill in the values into the tree in left-to-right order.