programming and ds closed

Question

In a binary tree,for every node the difference between the number of nodes in the left and right subtrees is atmost 2.If the height of the tree is h>0,then the minimum number of nodes in the tree is:

A)2^(h-1)     B)2^(h-1)+1

C)2^(h)-1     D)2^h

 

Answer is B) but explain the derived process clearly?

Comments

https://gateoverflow.in/3811/gate2005-it-50

---

Let there be n(h) nodes at height h.

In a perfect tree where every node has exactly

Two children, except leaves, following recurrence holds.

n(h) = 2*n(h-1) + 1

In given case, the numbers of nodes are two less, therefore

n(h) = 2*n(h-1) + 1 - 2

     = 2*n(h-1) - 1

Now if try all options, only option B  satisfies above recurrence.