The Gateway to Computer Science Excellence

+3 votes

+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 = 2^{2} . 2^{(H-3)} + 1 = 2^{(H-3)+2} + 1 = 2^{(H-1)} + 1.**

0

Nice explanation @shaik sir :)

I have just one doubt.

What is no.of nodes in left subtree ?

It shouId be equal tono.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$?

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?

+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 = 2^{2} * N(H-2) - 2 -1

= 2^{2} * ( 2 * N(H-3) - 1 ) - 2 - 1 = 2^{3} * ( N(H-3) ) - 2^{2} - 2 - 1

after K iterations,

= 2^{K} * ( N(H-K) ) - 2^{(K-1)} - ..... - 2^{2} - 2 - 1 )

= 2^{K} * ( N(H-K) ) - ( 2^{(K-1)} + ..... + 2^{2} + 2 + 2^{0} )

= 2^{K} * ( N(H-K) ) - ( 2^{(K)} - 1 )

= 2^{K} * ( N(H-K) ) - 2^{(K)} + 1

= 2^{K} * ( 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 2

h−1+1Another one answer is 2

h+1−1Why 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?

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

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

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

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

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

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.

52,315 questions

60,427 answers

201,750 comments

95,226 users