Unique property of a full binary tree

Question

I read a statement that was unclear to me, and was hoping to get some clarification.

It said that given a full binary tree with $n > 2$ leaves, there exists some internal node such that one third to two thirds of all $n$ leaves in the tree are its descendants.

From my understanding, I know each internal node in a full binary tree has 2 children. That said, the whole tree has $2n - 1$ nodes, which means $n - 1$ of them are internal nodes (not leaves).

I can come up with drawn examples where this is always the case, but I am not sure how to formally reason it. Any help would be greatly appreciated.

Answer 1

Let $T$ be a tree rooted at $r$ with $n > 2$ leaves, and let $\ell(u)$ denote the number of leaves in the subtree of $T$ rooted at node $u$.

Initially let $v=r$, then proceeds as follows:

1. If $\ell(v) \le \frac{2n}{3}$ then return $v$.
2. Otherwise, let $u$ be one of the children of $v$ with the largest $\ell(u)$, set $v=u$ and repeat from the first step.

Notice that, for every $v$ considered by the algorithm:

• $v$ is not a leaf (hence step 2 is well-defined). If $v$ were a leaf, then the parent $w$ of $v$ (which always exists) would satisfy: $2 \le \frac{2n}{3} < \ell(w) = 2 \ell(v) = 2$, a contradiction.

• $\ell(v) > \frac{n}{3}$. This is clearly true when $v=r$. For $v \neq r$, let $w$ be the parent of $v$. Since $\ell(w) > \frac{2n}{3}$, we must have $\ell(v) \ge \frac{\ell(w)}{2} > \frac{2n/3}{2} = \frac{n}{3}$.

The algorithm must terminate (at each iteration the depth of $v$ increases), therefore the returned vertex $v$ is not a leaf and satisfies both $\ell(v) > \frac{n}{3}$ (by the above property) and $\ell(v) \le \frac{2n}{3}$ (by the condition of step 1).

This proof is constructive and shows that $v$ can be found in $O(n)$ time (you can find all the values $\ell(v)$ with a postorder visit).