UGC NET CSE | December 2011 | Part 2 | Question: 50

Question

The number of nodes in a complete binary tree of height $h$ (with roots at level $0$) is equal to

• A. $2^{0} + 2^{1} + ….. 2^{h}$
• B. $2^{0} + 2^{1} + ….. 2^{h-1}$ 
• C. $2^{0} + 2^{1} + ….. 2^{h+1}$
• D. $2^{1} + ….. 2^{h+1}$

Answer 1

Option A is Ans

Height:--No of edges between root node to lowest descendent node

The total no. Of nodes in complete binary tree is depicted below:--

Answer 2

complete binary tree is filled left to right

and we know that maximum number of nodes possible in complete binary tree of height h = $2^{h+1}-1$

here,

option A)  $2^0+2^1+2^2+2^3+......+2^{h-1}+2^h = 1 + 2(\frac{2^h-1}{2-1}) = 1 + 2^{h+1} - 2$

$= 2^{h+1} - 1$

Comments

Thanx for d ans though there is no -1 in the option given above. Please can you clarify it?

---

that -1 comes after using GP fomula