Unique property of a full binary tree
Let $T$ be a tree rooted at $r$ with $n &gt; 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:


If $\ell(v) \le \frac{2n}{3}$ then return $v$. 
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} &lt; \ell(w) = 2 \ell(v) = 2$, a contradiction.
$\ell(v) &gt; \frac{n}{3}$. This is clearly true when $v=r$. For $v \neq r$, let $w$ be the parent of $v$. Since $\ell(w) &gt; \frac{2n}{3}$, we must have $\ell(v) \ge \frac{\ell(w)}{2} &gt; \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) &gt; \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).