UGC NET CSE | June 2009 | Part 2 | Question: 27

Question

In a full binary tree of height k, there are ______ internal nodes .

• A. 2k-1             
• B. 2k-1     
• C. 2k                 
• D. 2k+1

Answer 1

in a full binary tree each node has either zero or two children.  A complete binary tree is a full binary tree in which every leaf is at the same level.

I think they are trying to refer complete binary tree using full binary tree so answer is A. A complete binary tree has  2^k-1 internal nodes and  2^k leaves.

Answer 2

Full binary tree where every node other than leaf node have two children means every level is full and occupy maximum number of node possible at that level (in complete binary tree last level leafs may be not full means last level may not have maximum node possible).so we can say that every full binary tree is a complete binary tree but not vise versa.

Considering root at level 0

Now each node have two children so no. Of nodes at level

1st=2^(0);

2nd= 2^(2);

For kth level no of node is 2^(k);

So total no of node is sum of nodes at all the level which is a gp

Total node=2^(k+1) -1;

                =2*(2^k) -1;

So total nof ol leaf nodes is the node at kth level = 2^(k)= (2^k);

Total internal node=total node -leaf node

                                 =2*(2^k)-1-(2^k)

         =2*(2^k)-(2^k)-1

         =(2^k)-1;

  So option a is correct.