Return to Question

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.

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?

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?

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 sub-trees with at least $\ell$ leaves that can be found in $T$? To be more precise, each sub-tree is required to have 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?

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.

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?