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

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?

Solution 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).

Solution 2:

You answer yourself in the question.

The number of nodes is equal to $2^{k}-1$ where $k≥1$. So the minimum level is 1, not 0.

Thus the example is correct because it has 2 levels of depth: $2^{2}-1 = 3$

Solution 3:

A binary tree might be made by recieving goods, and working down until you find an empty slot for it.

The first item is called '1'. The second object in, supposing it's bigger than the first, is '11'. The third object in is called say '110', meaning it's bigger than '1', but smaller than '11'. As objects arrive, they acquire addresses like this. The next object might be smaller than '1', so it's '10'.

The depth of the tree is simply the longest recorded string, so the depth of the tree in the previous paragraph is 3 (ie the digits in '110').

The total possible names, is then the binary numbers from '1' to '111', where '111' is the length of the longest name (or depth). This equates to $2^d-1$, where $d$ is the depth. In a real tree, not all parts are occupied, so the population is less than the maximum it could hold.