The Gateway to Computer Science Excellence
+3 votes
848 views

in DS by
edited by | 848 views
+1
HINT: Read question One more time, It is saying P-Q<=2  where P and Q are no. of nodes in the left and Right Subtree and Not height of left and right subtree!

1 Answer

+14 votes
Best answer

the original image https://drive.google.com/open?id=1-Erqg7Y2xqXJL5YFyDZNh_GJ2Bxto7pT

But now i am interested to find it in general height.

we know that the no.of nodes of right side should be less than 2 at maximum only

===> for minimum no.of nodes, i consider  no.of right subtree nodes = no.of left subtree nodes - 2

===> Total nodes in that tree = no.of left subtree nodes + no.of right subtree nodes + 1 ( root node)

                                           = no.of left subtree nodes + ( no.of left subtree nodes - 2 ) + 1

                                           = no.of left subtree nodes + no.of left subtree nodes - 2  + 1

                                           = 2 * no.of left subtree nodes - 1

what is no.of nodes in left subtree ?

it should be equal to no.of nodes in h-1, where h is height of your tree

Total nodes in that tree = 2 * no.of left subtree nodes - 1

                         N(H) = 2 * ( N(H-1) ) - 1

for solving this recurrence relation, the base condition is N(H=3) = 5

using Back Substitution, we an solve it, the final value we can get

N(H) = 4 . 2(H-3) + 1 = 22 . 2(H-3) + 1 = 2(H-3)+2 + 1 = 2(H-1) + 1.

by
selected by
0

Nice explanation @shaik sir :)
I have just one doubt.

What is no.of nodes in left subtree ?
It shouId be equal to no.of nodes in h-1, where h is height of your tree

Can you please tell me how you get this? 

+1

mam, By seeing the image, h=3 which is in green color, should be use as left subtree as h=4.

if you didn't get that, follow

Can you please tell me how you get this? 

For getting a tree of height h,  let fix a node as root. then your left subtree or right subtree should have the height h-1, due to overall height is h.

By convention i go with left subtree as height h-1. Howmany nodes my left sub tree should have ?

it is like our original problem ( Howmany minimum Nodes the tree have with height h with given property ?)

∴ if my problem is N(H) then my new problem is N(H-1) and My right Subtree have ( N(H-1) - 2 )

 ===> N(H) = 1 (for root) + N(H-1) ( for left subtree ) + ( N(H-1) - 2 ) ( for right subtree )

 N(H) = 2 * ( N(H-1) ) - 1

0
@Shaik

how u got $N(H) = 4 . 2^{(H-3)} + 1$?

plz elaborate it

N(H) = 2 * ( N(H-1) ) - 1//this is fine

N(H=3) = 5// this line also fine

but then  how u got $N(H) = 4 . 2^{(H-3)} + 1$?
0

See this question https://gateoverflow.in/1210/gate2007-12

There is small difference between these two question 

One taking height difference 2 and another not taking it

Moreover, this question answer is $2^{h-1}+1$

Another one answer is $2^{h+1}-1$

Why this difference comes?

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

+1

but then  how u got N(H)=4.2(H−3)+1?

  N(H) = 2 * ( N(H-1) ) - 1

        = 2 * ( 2 * N(H-2) - 1 ) - 1  = 22 * N(H-2) - 2 -1

        = 22 * ( 2 * N(H-3)  - 1 ) - 2 - 1 = 23 * ( N(H-3) )  - 22  - 2 - 1

after K iterations,

        = 2K * ( N(H-K) )  - 2(K-1) - .....  - 22  - 2 - 1 )

        = 2K * ( N(H-K) )  - ( 2(K-1) + .....  + 22  + 2 + 20 )

        = 2K * ( N(H-K) )   - ( 2(K) - 1 )

        = 2K * ( N(H-K) )  -  2(K) + 1

        = 2K * ( N(H-K) - 1 )  + 1

let H-K = 3 ===> K = H-3 ===> the eqn turned into

        = 2(H-3) * ( N(3) - 1 )  + 1

        = 2(H-3) * ( 5 - 1 )  + 1

        = 2(H-3) * ( 4 )  + 1



See this question https://gateoverflow.in/1210/gate2007-12

There is small difference between these two question 

One taking height difference 2 and another not taking it

Moreover, this question answer is 2h−1+1

Another one answer is 2h+1−1

Why this difference comes?

those are different questions, you can't compare them.

For getting the answer for the question   https://gateoverflow.in/1210/gate2007-12

check Ayush Comment on it

0

why cannot we compare them?

See 1st question maximum number of nodes, i.e. Full Binary Tree

and 2nd one is for minimum number of nodes in AVL tree

rt?

+1
Mam, it is not AVL tree...

Even it is a AVL tree, how can you compare those formulas?
0

yes, not AVL tree, because height is taking difference upto 2, not less than 2

But we can tell 

1st one formula is not for height balanced

and 2nd one for height balanced

0
That means Catalan number will satisfy 1st formula

right?
0
Mam,How Catalan number will equal to the formula?
0

because for height =2 there will be 7 nodes and we can draw all binary tree from this

https://en.wikipedia.org/wiki/Catalan_number

ryt?

0

@Shaik Masthan

Here you have taken ..N(H) = 2N(LST) - 1

==>  N(H) = 2N(H-1) - 1

WHy we have taken height of LST as H-1 ..won't there be a case such that N(LST) = X and N(RST) = X-2 and

Height of LST < H-1 but Height of RST = H-1

0

won't there be a case such that N(LST) = X and N(RST) = X-2 and  Height of LST < H-1 but Height of RST = H-1

No, can't possible.

 

WHy we have taken height of LST as H-1

Note that minimum no.of nodes asked

+2

I got minimum 8 nodes at height 4 . is there anything wrong with my solution ?

+1
is root satisfying the given condition ?
0
got it. thanks .
0

@Shaik Masthan

let H-K = 3 ===> K = H-3 ===> the eqn turned into

why upto 3 have u taken? 

0
mam, that is base case, i assumed my base case is 3 due to i can manually calculate it.

you can take base case as 4, then you have to substitute the value of 4
0

@Shaik Masthan sir , condition of P and Q is given for h>0 , but root is at height 0, 

why we are applying this condition at root.

 

+1

condition of P and Q is given for h>0

that means when h=0, no need to check, but it doesn't mean don't check the root if h>1

0
someone please explain how the root doesn't satisfy the condition,I didn't get it
0
Solving recurrences is easier if we solve them as given in Rosen(Solving non homogeneous equation).
0

@Shaik Masthan-In extension to solve the recurrence you have derived.

$N(h)=2N(h-1)-1$......(1)

The associated homogenous recurrence relation is

$N(h)=2N(h-1)$

So, solution to this is $C2^h.$

Particular solution will be of the form

$d$

Substituting this in 1 to get $d=1$.

So, $N(h)=C2^h+1$

Base case is $N(0)=1$

$1=C+1$

$C=0.$

But that makes final solution as $N(h)=1$

Where I am going wrong?

@tusharp-I think you were talking about this.Please help.

0
It is like T(n) = 2 T(n-1) - 1

equation becomes x-2 = 0

Solution : An= alpha (2)^n + particular solution

As RHS is constant term its soln will be simply A(constant)

substituting this in eqn we get A=2A -1 => A =1

Sol becomes An= alpha (2)^n +1

We know base condition A3 =5 => alpha = 1/2

final solution = 1/2 (2)^n -1 => 2^n-1 +1
0

@tusharp-Why are you taking base condition only $A(3)=5$. $A(0)=1$ is also valid because for height 0, minimum 1 node is required.

0
However $A(1)=2$ also gives the correct constant value for A.But why not $A(0)=1$?
0
Hello @Ayush did you find out why not we consider A(0)=1 as base case?
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,427 answers
201,750 comments
95,226 users