Recurrence for number of nodes

Question

I have a doubt in this question :

https://gateoverflow.in/3811/gate2005-it_50

I am posting this, as there is a very low probability my comment will be replied.

I wanted to progress in the solution by forming the recurrence . This was my logic :

T(h) : No. of nodes at height h

T(l,h-1) : No. of nodes in the left subtree having height h-1

T(r,h-1) : No. of nodes in the right subtree having height h-1

T(h) = T(l,h-1)+T(r,h-1)+1

Min. no. of nodes occur when diff between T(l,h-1) and T(r,h-1) is 2.

Recurrence :

T(h) = T(r,h-1)+2+T(r,h-1)+1

T(h)=2T(h-1) + 3

This is not correct, as T(1) should be 2. It gives 5; T(0)=1

Can anynody help me with correct recurrence?

Answer 1

- You almost got that..

Min. no. of nodes occur when diff between T(l,h-1) and T(r,h-1) is 2.

- Yes, correct till this.

Recurrence :

T(h) = T(r,h-1)+2+T(r,h-1)+1

- Here, you are replacing T(l,h-1) with T(r,h-1) + 2. That means you are adding 2 more nodes to left subtree.

Why add 2 more nodes? We need min number of nodes, so just subtract 2 nodes.. i.e

Recurrence :

T(h) = T(r,h-1)-2+T(r,h-1)+1

T(h)=2T(h-1) - 1;

T(1)=2 This should be considered as base condition as h>0

Comments

Thanks!! Your explanation is correct