Efficient way to find the i-th size in a BST
(Please check the problem statement: having sub-tree sizes at each vertex available in constant time is very useful to find the $i$−th smallest/largest element/key (with $2$ being the 3rd smallest element in $1, 2, 2, 2, 3, 4$).)  

For finding the $i$−th largest size, notice the tree to be a max-heap with respect to sub-tree sizes.
In search of the $i$−th smallest size, assume that the tree is perfectly balanced but for the path to one leaf, which is longer by i ($∄j: i = 2^j-1$). Before encountering that path/vertex, all sizes no larger than i will have been of the form ($2^j-1$). As you don't know if and where such a path/vertex exists, you will have to visit on the order of all n vertices.
Unless you find a way to know the $i$−th size among $Ο(n)$ candidates faster, this will be $Ω(n \log(i))$ in $Ο(i)$ space. (This depends on how much additional memory can be used, e.g., with $Ο(n)$ memory, you can do a counting sort of sizes encountered in $Ο(n)$ time.)

Run-time can be reduced by properly bounding the search:
Every non-empty tree will contain at least one leaf, so if i is $1$, return $1$.
For $1 &lt; i$, keep track of the highest size s such that every size up to s is known to have been encountered. When s reaches $i$, return that. Never descend from vertices with size no greater than s.