The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.

Question

I am confused with this statement

The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$.

How come this is true. Lets say I have the following tree

    1
   / \
  2   3

Here the depth of the tree is 1. So according to the formula, it will be $2^1-1 = 1$. But we have $3$ nodes here. I am really confused with this depth thing.

Any clarifications?

Answer 1

It should be $2^{k+1}-1$. The proof is as follows: In a full binary tree, you have 1 root, 2 sons of that root, 4 grandsons, 8 grand-grandsons and so on. So the total number of nodes is the sum of the geometric series:

$$1+2+4+8+\dots +2^{k} = \frac{2^{k+1}-1}{2-1}=2^{k+1}-1$$

where $k$ is the depth (i.e. for $k=0$ we have 1 node).

Answer 2

We assume that the root of a binary tree is on level 1, so in your mentioned tree, the depth is 2 not 1, so (2 to the power 2 ) - 1 = 3 nodes.