# Prove any binary tree with $n$ nodes has at least $1+\log_2 n$ levels

Prove that any binary tree with $n$ nodes has at least $1+\log_2 n$ levels. I tried setting $n=8$ and plugging in $8\geq\log_2 8 = 8\geq 3$. But I'm not sure how I can prove this by induction.

• How does showing that $8\geq 3$ establish anything about binary trees? You need to relate the number of leaves and numebr of levels, not $n$ and $\log n$. – David Richerby Sep 21 '14 at 23:56
• What does the shallowest binary tree on $n$ nodes look like? There will be 1 node at the root (level 0), 2 child nodes at level 1, 4 at level 2 so for $n = 7 (=1+2+4)$ there must be at least 2 levels. Generalize this. – Rick Decker Sep 22 '14 at 0:56
• – d'alar'cop Sep 22 '14 at 4:04
• The induction is elementary; do you understand induction in principle? What has to be the anchor here? Over which quantity should we do the induction? – Raphael Sep 22 '14 at 6:35

Hint: A binary tree with $1+h$ levels contains at most $1+2+2^2+\cdots+2^h = 2^{h+1}-1$ vertices.