UGC NET CSE | September 2013 | Part 2 | Question: 11

Question

The min. number of nodes in a binary tree of depth d (root at level 0) is

• A. $(2^d + 1)$
• B. $(2^{(d+1)} - 1)$
• C. $d$
• D. $d + 1$

Answer 1

Answer will be 4) d + 1

Notice that its just a binary tree. A binary tree can have maximum of two children, but not more. 

Here its asking the minimum, hence we will consider only one node at each level. Hence for the depth of d, we need d + 1 nodes.

For example consider this tree. Each and every node 1 child.