19
$\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?

  • 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

34

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