0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.