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?