binary search tree size calculation

Question

how do I calculate the number of elements a binary search tree can hold if have the height? For example a tree of height 3 can have 7 elements (7=1+2+4), and a tree of height 4 can have 15 elements (15=1+2+4+8).

Answer 1

A binary tree of height $n$ can hold $1+2+4+...2^{n-1}=2^n - 1$ elements.

This is because if $s= 1+2+4+...2^{n-1}$ then $2s=2+4+8+...2^n$ so when you subtract $s$ from $2s$ everything except the $2^n$ and the $1$ cancel to give $$2s-s=s=2^n-1$$