GATE CSE
First time here? Checkout the FAQ!
x
0 votes
43 views

I have a doubt in this question :

http://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?

asked in Algorithms by Loyal (3.9k points)   | 43 views

1 Answer

+1 vote
Best answer
- 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
answered by Loyal (3.6k points)  
selected by
Thanks!! Your explanation is correct


Top Users Sep 2017
  1. Habibkhan

    8312 Points

  2. Warrior

    2862 Points

  3. rishu_darkshadow

    2796 Points

  4. Arjun

    2766 Points

  5. A_i_$_h

    2526 Points

  6. manu00x

    2094 Points

  7. nikunj

    1980 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1810 Points

  10. SiddharthMahapatra

    1718 Points


26,283 questions
33,842 answers
80,383 comments
31,193 users