+13 votes
4.1k 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 | 4.1k 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

## 3 Answers

+26 votes
Best answer
$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.
answered by Boss (14.4k points)
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.
0

@Ayush Upadhyaya

If height is defined as number of nodes from root to leaf then it will be 2^h - 1 right ?

+7 votes

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

answered by Loyal (8k points)
+4 votes

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

answered by Active (2.6k points)
Answer:

+18 votes
2 answers
1
+14 votes
2 answers
2
+20 votes
2 answers
3
+14 votes
3 answers
4
+34 votes
2 answers
5
+19 votes
5 answers
6
+18 votes
3 answers
7