Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

   / \
  2   3

Here the depth of the tree. 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?

share|cite|improve this question
Even simpler: A binary tree with depth 0 has 1 node (the root), not 0 nodes. But check your source's definitions. If they define depth as the number of nodes on the longest root-to-leaf path, instead of the (more standard) number of edges on the longest root-to-leaf path, then their statement is correct. – JeffE May 6 '12 at 15:14
@rajansthapit what is the name of tile/author of the book? Gadi has the correct answer. – Kirthi Raman May 6 '12 at 20:10
4k+ views and not a single upvote? Time to change that! :D – zerosofthezeta Nov 12 '13 at 23:56

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

share|cite|improve this answer
Yeah, it should have been like that but I have seen the one given above at many places. I really believe people should follow a standard when defining the depth – rajan sthapit May 6 '12 at 15:21
Please give accurate references; don't talk about "many places" but give the name of a concrete book (and page...) so we can check where the misunderstanding is. – Gadi A May 6 '12 at 15:22

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$

share|cite|improve this answer

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.

share|cite|improve this answer

According to your formula. the depth is not equal to 1 here. depth starts from 1 to onwards. and level of the tree starts from 0. So here depth is 2. you take 2^2 - 1 = 3 nodes. here k = 2.

In some books you will find depth starting from 1 and level of the tree starting from 0 and in other books you find it the other way round. But from where you have taken this formula here depth starts from 1 (i.e. minimum depth can be 1)

share|cite|improve this answer

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.

share|cite|improve this answer

protected by Zev Chonoles Nov 7 '15 at 5:36

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.