The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 votes

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 by Veteran (59.8k points) | 4.3k views
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.

Correct Answer: $C$
answered by Boss (14.5k points)
edited by
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.

@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 Boss (11k 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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,403 questions
53,576 answers
70,852 users