# Unique property of a full binary tree

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.

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