Question

Consider a binary tree, where for every node P - $Q\le 2$, where P represents number of nodes in left sub tree for node S and Q represents the number of nodes in right sub tree for node S for h > 0. The minimum number of nodes present in such a binary tree of height h = 4 will be

• A. 6
• B. None of these
• C. 8
• D. 9

Answer 1

The correct option is D 9

(c)
It can be seen that the minimum node possible in such a tree of height H will be,

$N\left(h\right)=[2^{h-1}+1]$
Therfore putting H = 4, we get, $N\left(4\right)=2^3+1=9$
Hence option (c) will be answer.