Question

Show that if L ≥ 2, then every binary tree with L leaves contains a subtree having between L/3 and 2L/3 leaves, inclusive.

Answer 1

Answer and Explanation:

Proof by the using contradiction:

Let us assume that it isn't the situation and the statement is incorrect. Accordingly, the quantity of leaves in a subtree is either not as much as $\frac{L}{3}$ or more noteworthy than $\frac{2L}{3}$. Presently, on the off chance that we consider the subtree with number of leaves greater than $\frac{2L}{3}$ leaves, we can say that there exists a subtree of the subtree referenced before that has more than $\frac{4L}{9}$ leaves. Be that as it may, once more, $\frac{L}{3}\leq \frac{4L}{9} \leq \frac{2L}{3}$ thus the first explanations holds.