3
$\begingroup$

I'm wondering if anyone can help me prove (or disprove) this statement?

Say there is a rooted full binary tree (each non-leaf node has exactly two children) with a height of $h$, an average height of $t$, and $l$ leaves. Then for $k \geq 1$ there are at most $\frac{l}{k}$ leaves above a height of $kt$.

I think the statement is correct and basically I've been trying to assume the contrary and come up with a contradiction using the average height -- but no success.

  • 0
    Further clarification, the average height of a tree is the sum of the height of the leaves, divided by the number of leaves. The height of non-leaf nodes is not counted.2012-08-16

2 Answers 2

1

I suppose the terminology of height of a node may be confusing here, so let's make it clear first how I interpret it:

The height of the root is 0; if a node has height $j$, its children has height $j+1$. Being above means having larger height, i.e. further from the root. Thus, one thinks of the root at the bottom and the leaves at the top, not the other way around.

If the tree has $m_j$ leaves at height $j$, where $h$ is the maximal height (i.e. $\sum_j$ means $\sum_{j=0}^h$), then $l=\sum_j m_j$ and $l\cdot t=\sum_j jm_j$. Let me rephrase the problem slightly: for any $a>0$ (where $a=kt$ in the original), there are at most $lt/a$ leaves with height $j\ge a$. This follows from $\sum_{j\ge a} m_h =\frac{1}{a}\sum_{j\ge a} am_j \le\frac{1}{a}\sum_{j=0}^h jm_j =\frac{lt}{a}. $

The requirement that $k\ge1$ (i.e. $a\ge t$) is not required, only that $a>0$. Of course, the only interesting values of $a$ are integers.

It may also be noted that the result doesn't make use of the fact these are leaves on a binary tree: they are just leaves with values (in this case height) attached to them.

1

The tree shown below is a counterexample to the current version of the conjecture.

                    o                      / \                     o   o                    / \                   o   o 

Here $h=2$, $t=\frac15(1\cdot0+2\cdot1+2\cdot2)=\frac65$, and $\ell=3$. Take $k=\frac85$; then $\frac{\ell}k=\frac{15}8<2$, but there are $2$ leaves of height $2>\frac{48}{25}=\frac65\cdot\frac85=kt$.

  • 0
    (Now that the OP has clarified, incidentally, the average height $t$ of your tree by his rules is 5/3, so this example no longer works.)2012-08-16