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.7k points) | 3.4k 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.
answered by Boss (14.4k 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.
+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 (7.5k 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.5k 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

44,284 questions
49,776 answers
65,856 users