The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 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.5k points) | 2.6k 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

+25 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.2k points)
edited by
+6 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.6k 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.3k 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

37,999 questions
45,495 answers
48,630 users