# Efficient way to find the i-th size in a BST

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 subtree

Write an algorithm selection(T,i) that gets a Tree with size at each vertex and return the $i-$th smallest/largest size in the tree

Attempt:

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_6


The 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.

• Yes, this is the input, there is no restrictions on additional memory Commented Jan 5, 2017 at 10:25
• In your example, is 2 the second weight or the fourth? Commented Jan 5, 2017 at 10:55
• '2' is the second size Commented Jan 5, 2017 at 11:23

(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.

• Could you explain why would you do that? Isn't it just worse than the obvious $O(n)$ solution? Commented Jan 5, 2017 at 14:22
• @quicksort: Please sketch the obvious O(n) solution. Commented Jan 5, 2017 at 14:23
• Collect the weights into an array. Median of medians. Commented Jan 5, 2017 at 14:24
• @quicksort: Median of medians quickselect, rather. (While that's the Unless you find a way to know the i−th size among O(n) candidates faster part,) somehow, I was under the impression that $O(\log n)$ memory wasn't admissible. Commented Jan 5, 2017 at 14:26
• (Does quickselect support $i$-th unique value?) (Then again, you could use a counting sort in $O(n)$ space.) Commented Jan 5, 2017 at 14:33