3.4k views

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

1. $2^h -1$

2. $2^{h-1} -1$

3. $2^{h+1} -1$

4. $2^{h+1}$

asked in DS | 3.4k views
0
If height of tree tree start with 0 then? I think answer depends on whether height start from zero or 1. Correct me if I am wrong

$2^{h+1} - 1$ just try this taking a small complete binary

never try to remember these formulae as remembering formulae is an overhead try to take examples in such cases.
edited by
+3
The maximum number of node will occur when each level is completely filled from height 0 to h.

At each height, we have a maximum of $2^h$ nodes

$\sum_{k=0}^{h}2^k=2^0+2^1+2^2+....+2^h=\frac{2^{h+1}-1}{2-1}=2^{h+1}-1$ nodes.

At maximum tree is given as above

So maximum height = 2 (15 - > 10 -> 8) or other all are same height

Put h = 2 in option and find number of nodes

A- 22 -1 = 3  wrong

B- 21-1 = 1 wrong

C- 23-1 = 7 correct

D- 23 = 8 wrong

SO option C is correct option

height H=0 ( only root node ) , no of node N=1=20

H=1 , N=21

... so on

total =20 +21+22+.......2H =2H+1-1

Ans is C

1
2