GATE CSE 2007 | Question: 12

Question

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:

• A. $2^h -1$

• B. $2^{h-1} -1$

• C. $2^{h+1} -1$

• D. $2^{h+1}$

Comments

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

---

If we take a perfect binary tree, all nodes are completely filled — including the last level. In this case, it also satisfies the condition of a Complete Binary Tree (CBT).

 

Let’s assume the height h=2

• The root node is at height 2:
    → It has 2^0 = 1 node

• The next level (height 1) has:
    → 2^1 = 2 nodes

• The last level (height 0) has:
    → 2^2 = 4 nodes

So the total number of nodes is:

2^0+2^1+2^2=1+2+4=7

This is a geometric series of the form:

Sum=a⋅(r^n - 1)(r - 1)

Where:

• a=1=2^ 0 (first term)

• r=2 (common ratio)

• n=h+1  (number of terms from 0 to h)

So:

Total nodes= 2^(h+1) - 1

---

answer is Option C.

 

---

For a given binary tree height h:

Maximum number of nodes possible in case of Perfect binary tree

Minimum number of nodes possible in case of Skewed binary tree

Note: take example and check but don't remember the maximum nodes blindly

Answer 1

$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$

Comments

But it didnt even mentioned it is complete binary tree???,

---

@PRANAV M Question is asking about the maximum number of nodes for a given height,so number of nodes will be maximum (i.e. tree is most dense) when it is a full binary tree. Also keep in mind the difference between Full and Complete binary tree, they are not the same.

---

@Gaganjot _Kaur the tree for this is Perfect Binary tree(every level fully filled) as Perfect Binary tree implies Full Binary tree(every node have 0 or 2 children) and not just Full binary tree as Full binary tree do not implies Perfect binary tree .

Answer 2

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- 2² -1 = 3  wrong 

B- 2¹-1 = 1 wrong 

C- 2³-1 = 7 correct

D- 2³ = 8 wrong 

SO option C is correct option

Answer 3

height H=0 ( only root node ) , no of node N=1=2⁰

H=1 , N=2¹

... so on 

total =2⁰ +2¹+2²+.......2^H =2^H+1-1

Ans is C

Answer 4

=2$^0$+2$^1$+2$^2$+...+2$^h$ this a  gp

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

Answer 5

We are required to find the maximum number of nodes. Maximum number of nodes will occur in the case of a Perfect tree. We just need to calculate relation between the height of Perfect tree and its number of nodes.

Height zero :  one node - > 2^0

Height one : two node -> 2^1

Height two : four nodes -> 2^2

.....

Height h : 2^(h) nodes

 

Now if you some all the nodes at various heights , you will get the total number of nodes.

 

 N = 2^0 + 2^1 + 2^2 + 2^3 ...... + 2^h

(Sum of a Geometric Progression = first term * (1-ratio^number of terms)/(1-ratio))

=>  N =  2^(h+1) - 1

 

 

 

 

Answer 6

We are required to find the maximum number of nodes. Maximum number of nodes will occur in the case of a Perfect tree. We just need to calculate relation between the height of Perfect tree and its number of nodes.

Height zero :  one node - > 2^0

Height one : two node -> 2^1

Height two : four nodes -> 2^2

.....

Height h : 2^(h) nodes

 

Now if you some all the nodes at various heights , you will get the total number of nodes.

 

 N = 2^0 + 2^1 + 2^2 + 2^3 ...... + 2^h

(Sum of a Geometric Progression = first term * (1-ratio^number of terms)/(1-ratio))

=>  N =  2^(h+1) - 1