Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. 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|improve this question
1  
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

5 Answers 5

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|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: $2^{2}-1 = 3$

share|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|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|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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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