NIELIT 2017 OCT Scientific Assistant A (IT) - Section B: 2

Question

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number number of nodes in a binary tree of height $h$ is 

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

Answer 1

option C will be correct.

At level 0 no. of nodes = 2^0

At level 1 no. of nodes = 2^1

At level 2 no. of nodes = 2^2

similarly,At level h-1 no. of nodes = 2^(h-1)

sum them 2^0 + 2^1 + 2^2 ..... + 2^(h -1)

sum = 2^(h +1) - 1

no. of nodes = 2^(h + 1) - 1