55 A Combinatorial Lemma

Lemma

Let $T$ be a binary tree. Then there is a subtree $S$ of $T$ s.t.
$\frac{1}{3}|T|<|S|\le \frac{2}{3}|T|$

Proof Idea

Starting from the root, keep taking the largest immediate subtree until one falls into the required range. At each step the subtree at most halves in size, and so the first time the subtree has size $\le \frac{2}{3}|T|$ it must also have size $>\frac{1}{3}|T|$.