16
$\begingroup$

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?

  • 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.2012-05-06
  • 0
    @rajansthapit what is the name of tile/author of the book? Gadi has the correct answer.2012-05-06
  • 1
    4k+ views and not a single upvote? Time to change that! :D2013-11-12
  • 0
    Number of **internal nodes in a perfect** binary tree of depth $k$ is $2^k-1$, $k \geq1$ . You may have read it wrong. I can prove it to you but I can not create an answer because of low rep.2017-11-08

5 Answers 5

29

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

  • 0
    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 depth2012-05-06
  • 4
    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.2012-05-06
  • 0
    What is a general formula for any n-ary tree?2018-10-11
5

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$

  • 0
    you should mention that it's for level k only. the total number of nodes in the tree is 2^(k+1) as Gadi suggests2017-09-09
  • 0
    All answers lie in the question. It is the teacher whose voice raises them from their slumber and illuminates hidden truths.2017-10-09
1

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.

0

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.

0

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)