# Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$

I was able to prove that $$size(t) \leq 2^{h(t)} - 1$$ for any binary tree $$t$$, however I wasn't able to do anything reasonable with this statement.

I know it's a proof by induction and that the inductive hypothesis is the following:

$$size(l) < 2^{h(l)} \\ size(r) < 2^{h(r)}$$

where $$l$$ and $$r$$ are the left and right subtrees of the tree $$t = \langle l,v,r \rangle$$. Usually what I'd do is start from $$size(\langle l,v,r \rangle)$$ and work my way up to $$< 2^{h(\langle l,v,r \rangle)}$$. However I wasn't able.

## 1 Answer

If a binary tree has height $$h$$ then it has at most 1 node at depth 0, at most 2 nodes at depth 1, ..., at most $$2^{h-1}$$ nodes at depth $$h-1$$ (the maximal depth), and so at most $$1+2+\cdots+2^{h-1} = 2^h-1$$ nodes in total.

You can also prove this by induction. When $$h=1$$, the tree consists only of a root, so at most $$1=2^h-1$$ vertices. Given a tree of height $$h$$, its two subtrees have height at most $$h-1$$, and so together contain at most $$2(2^{h-1}-1)$$ vertices. Together with the root, the tree contains at most $$2(2^{h-1}-1)+1=2^h-1$$ vertices.