UGC NET CSE | December 2014 | Part 2 | Question: 25

Question

A full binary tree with $n$ leaves contains

• A. $n$ nodes 
• B. $\log_{2} n$ nodes 
• C. $2n –1$ nodes
• D. $2^{n}$ nodes 

Answer 1

Answer : 2n-1 nodes

A full binary tree  is a tree in which every node other than the leaves has two children

       

No of leaves	No of nodes	Result
first diagram has 2 leaves	total no of nodes is 3	2n - 1  = 2*2 - 1 = 3
second diagram has 4 leaves	total no of nodes is 7	2n - 1 =  2*4 - 1 = 7
third diagram has 8 leaves	total no of nodes is 15	2n - 1 = 2*8 - 1 = 15

Answer 2

Ans C

A full binary tree with nn leaves contains n-1 internal nodes.

Total nodes= internal nodes + leaves = n-1 + n

= 2n-1