Prove that in a binary tree there exists a leaf with depth at least $\log_2 n$

Question

It can be certainly tackled with induction method, but I'm not sure what metrics to use for induction. Hints will be appreciated. Also root level $= 0$.

Answer 1

HINT: Show by induction on $n$ that a perfect binary tree of depth $n$ has $2^{n+1}-1$ vertices. If a binary tree $T$ has no leaf of depth at least $n$, then the depth of $T$ is at most $n-1$, so $T$ has at most $2^n-1$ vertices. Now take logs base $2$.