NIELIT 2016 DEC Scientist B (CS) - Section B: 42

Question

The maximum number of nodes in a binary tree of level $k, k\geq1$ is:

• A. $2^k+1$
• B. $2^{k-1}$
• C. $2^k-1$
• D. $2^{k-1}-1$

Answer 1

 

Total number of level=$k$ 

At  level 0 number of node=$ 2^{0} $

 At level 1 number of node =$2^{1}$

 At level 2 number of node =$2^{2}$

 At level 3 number of node =$2^{3}$

 At level 4 number of node =$2^{4}$

 At level 5 number of node =$2^{5}$..

.

.

.

.At level k number of node =$2^{k-1}$

Total number of node in complete binary tree=$ 2^{0} $+$2^{1}$+$2^{2}$+$2^{3}$+$2^{4}$.....................$2^{k-1}$

$\left \{  1(2^{k}-1)/2-1\right \}$

=$2^{k}-1$

 

Answer 2

Level => No. of nodes

1 => 1

2 => 3

3 => 7

and so on....

Hence, option C is the correct option.

Answer 3

Since, they are asking in terms of levels answer would be 2^k -1