0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Yes, this is the input, there is no restrictions on additional memory $\endgroup$
    – Error 404
    Commented Jan 5, 2017 at 10:25
  • $\begingroup$ In your example, is 2 the second weight or the fourth? $\endgroup$
    – greybeard
    Commented Jan 5, 2017 at 10:55
  • $\begingroup$ '2' is the second size $\endgroup$
    – Error 404
    Commented Jan 5, 2017 at 11:23

1 Answer 1

0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Could you explain why would you do that? Isn't it just worse than the obvious $O(n)$ solution? $\endgroup$
    – quicksort
    Commented Jan 5, 2017 at 14:22
  • $\begingroup$ @quicksort: Please sketch the obvious O(n) solution. $\endgroup$
    – greybeard
    Commented Jan 5, 2017 at 14:23
  • $\begingroup$ Collect the weights into an array. Median of medians. $\endgroup$
    – quicksort
    Commented Jan 5, 2017 at 14:24
  • $\begingroup$ @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. $\endgroup$
    – greybeard
    Commented Jan 5, 2017 at 14:26
  • $\begingroup$ (Does quickselect support $i$-th unique value?) (Then again, you could use a counting sort in $O(n)$ space.) $\endgroup$
    – greybeard
    Commented Jan 5, 2017 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.