Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ leaves that can be found in $T$? Here, by a "rooted sub-tree", I mean a sub-tree that consists of a vertex and all its descendants, and we are looking for sub-trees that contain at least $\ell$ leaves of the original tree.

A naive answer would be $L/\ell$. However, it is easy to see that if $\ell>2$, the answer might be $1$: for example, this is the case if $T$ is the tree in which every internal vertex has at least one leaf as a child.

In the latter example, the tree is very unbalanced. It seems that if the tree is more balanced, we should expect an answer that is closer to $L/\ell$.

I have a non-trivial argument that shows that if $T$ is of depth $d$, then there are always at least $\frac{L}{O(d^2 \cdot \ell)}$ disjoint trees with at least $\ell$ leaves. My question is whether something like this is already known, or follows easily from some known theorem?

  • $\begingroup$ When you require a subtree to have at least $\ell$ leaves, do you mean leaves \emph{of the original tree} or just any vertices which happen to be leaves in the subtree? $\endgroup$ – monkeymaths Dec 20 '15 at 22:23
  • $\begingroup$ Sorry, tou are right - I meant leaves of the original tree. $\endgroup$ – Or Meir Dec 21 '15 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.