2
You problem is solved trivially in order statistic trees, where each node has an additional size attribute, and many answers have already mentioned this situation.
So what to do first is to calculate and memorize size for each node ($O(|V|)$), and then do a BST search to find the node with rank $|V|/2$, which is $O(\log(|V|))$ for balanced trees.
This ...
Only top voted, non community-wiki answers of a minimum length are eligible
