4
$\begingroup$

I want to show the following: Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.

My approach: First thing I did was to draw a binary tree and think about the problem and what I could do.

First I consider $k \leq \frac{2n}{3}$: If I consider a complete binary tree, then the "best case" where a subtree has the most leaves possible is where $k= \frac{n}{2}$. For an argument I tought of choosing the root of the subtree to be on the first level of the tree.

I think one could argue similarly for $\frac{n}{3} \leq k$, but what I got so far does not seem very "substantial" to me. My question is: How would one proof this statement?

$\endgroup$
5
  • $\begingroup$ You could try to use induction on the level of the tree. If $l$ denotes the level. You need to check that the inequality holds for $l=1$. After that consider the inequality holds for $l=j$, show that it has to hold for $l=j+1$. $\endgroup$
    – Philip
    Commented Jun 20 at 1:06
  • 1
    $\begingroup$ Are you sure this is true? A single node is a binary tree with $n=1$ leaves. But there are no subtrees with $\frac{1}{3} \leq k \leq \frac{2}{3}$ leaves since such a $k$ is not integral. $\endgroup$
    – MathematicsStudent1122
    Commented Jun 20 at 1:10
  • $\begingroup$ @MathematicsStudent1122 You were right. I just wanted to lay down the idea. $\endgroup$
    – Philip
    Commented Jun 20 at 1:12
  • $\begingroup$ So, if the tree has $n$ leaves and a subtree $k$ leaves up to level $j$. Then up to level j+1 the tree has at least $n$ and at most $2n$ leaves. Similary the subtree has then at least $k$ and at most $2k$ leaves. How can I now use the $\frac{n}{3} \leq k\leq \frac{2n}{3}$ to show that it also holds for the level $j+1$? $\endgroup$
    – NTc5
    Commented Jun 20 at 1:15
  • $\begingroup$ @MathematicsStudent1122 Do you have an idea on how to show this? $\endgroup$
    – NTc5
    Commented Jun 20 at 4:45

1 Answer 1

Reset to default
3
$\begingroup$

Given a binary tree $T$ with $n$ vertices, let $v$ be any vertex of $T$ with these two properties:

  • The subtree rooted at $v$ has more than $n/3$ leaves.
  • Out of all vertices satisfying the first bullet point, $v$ is the furthest from the root.

The second bullet point implies that both of $v$’s children have at most $n/3$ leaves in their subtrees. Therefore, the subtree rooted at $v$ has at most $n/3+n/3=2n/3$ leaves, so this is our desired subtree.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .