# Bounds on how far away most leaves are from the average height of a binary tree

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.

-
Can you clarify what you mean by the word 'above' in your statement? It has two distinct plausible interpretations: 'whose height is larger than the height $kt$', or 'which are visually/metaphorically 'above' the height $kt$, in the sense that their height is less than that'... – Steven Stadnicki Aug 15 '12 at 23:31
Sorry yes that is rather confusing. I meant the first interpretation. A leaf of height 3 is "above" a node of height 2. – PowerFace Aug 16 '12 at 16:02
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. – PowerFace Aug 16 '12 at 16:04

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.

-

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$.

-
It's not clear in what sense the poster means the phrase 'above' - it could as easily mean 'whose height is less than $kt$', esp. since they don't use the word 'height' before they use above. – Steven Stadnicki Aug 15 '12 at 23:29
@Steven: I suppose that it’s barely possible, but it would be completely unidiomatic. – Brian M. Scott Aug 15 '12 at 23:34
It depends on the idiom one's used to, I suppose. I've often seen a node's ancestors referred to as the nodes above it... – Steven Stadnicki Aug 15 '12 at 23:35
@Steven: But here we’re talking about numbers, not nodes. Besides, $\ell/k$ decreases as $k$ increases, as does the number of nodes of height greater than $kt$. – Brian M. Scott Aug 15 '12 at 23:36
True - I'd missed the sense of the dependency on $k$, which makes your interpretation much more likely. – Steven Stadnicki Aug 16 '12 at 1:16