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
`(L)/(3)` or more noteworthy than
`(2L)/(3)`. Presently, on the off chance that we consider the subtree with number of leaves greater than
`(2L)/(3)` leaves, we can say that there exists a subtree of the subtree referenced before that has more than
`(4L)/(9)` leaves. Be that as it may, once more,
`(L)/(3)\leq (4L)/(9) \leq (2L)/(3)` thus the first explanations holds.