GATE CSE
First time here? Checkout the FAQ!
x
0 votes
29 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.4k points)   | 29 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 Active (1.7k points)  
selected by
Thanks!! Your explanation is correct

Related questions

Top Users Jan 2017
  1. Debashish Deka

    8126 Points

  2. sudsho

    5042 Points

  3. Habibkhan

    4706 Points

  4. Vijay Thakur

    4458 Points

  5. Bikram

    4348 Points

  6. saurabh rai

    4212 Points

  7. Arjun

    4010 Points

  8. santhoshdevulapally

    3722 Points

  9. GateSet

    3292 Points

  10. Sushant Gokhale

    3286 Points

Monthly Topper: Rs. 500 gift card

19,122 questions
24,034 answers
52,724 comments
20,276 users