The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
2.3k 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 by Veteran (59.4k points) | 2.3k views

3 Answers

+23 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.1k points)
edited by
+5 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 (6.4k 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.2k points)


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

35,506 questions
42,827 answers
121,678 comments
42,181 users