NIELIT 2016 MAR Scientist C - Section C: 31

Question

A full binary tree with $n$ non-leaf nodes contains

• A. $\log_ 2 n$ nodes
• B. $n+1$ nodes
• C. $2n$ nodes
• D. $2n+1$ nodes

Comments

Full binary tree is a tree in which every node is having either 0 or 2 children.

In case of full binary tree if n non-leaf nodes are there, then there must be 2n+1 nodes.

Answer 1

In full tree , the node will either have 2 or no children. 

Thus 1 node has 2 children

2 node has 4 children

3 nodes have 6 children

hence “n” internal nodes have 2n+1 children (1 for including the root)

Answer 2

The relationship between external(leaf) nodes and internal nodes for binary tree is: $$L = i +1$$

According to ques, $i = n$ so using formula,

$$L = n+1$$

Since tree is made up of internal and leaf nodes

Therefore, Total no. of nodes(N) = $L +i$

So , $$N = n+1+n$$

$$Ans:N = 2n+1$$