Given the following definition of binary search tree:$$\text{size}(t)=\cases{0\qquad\qquad\qquad\qquad\qquad\qquad t=\text{ null}\\1+\text{size(t.left)+size(t.right)}\qquad\text{otherwise}}$$for each vertex in the tree t.size contain the size of it's subtreeWrite an algorithm  selection(T,i) that gets a Tree with size at each vertex and return the $i-$th smallest/largest size in the treeAttempt:I discovered that the size of a vertex is the number of vertices that there are in the specific root:e.g:                              V_1                             /   \                           V_2    V_3                           /      / \                         V_4     V_5 V_6The size of $V_4,V_5,V_6$ is: $1+0=1$The size of $V_2$ is: $1+1=2$The size of $V_3$ is: $1+1+1=3$The size of $V_1$ is: $1+3+2=6$Now to scan all vertices in the tree using preorder or postorder and to find the $i-th$ size, running time $O(|V|)$,I am looking for something more efficient.
Efficient way to find the i-th size in a BST
algorithms;data structures;runtime analysis
(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 < 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.