The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

asked in DS by (165 points)
edited by | 513 views
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

+11 votes
Best answer

the original image

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.

answered by Veteran (60.8k points)
selected by

@Shaik Masthan

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

why upto 3 have u taken? 

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

@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.



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

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

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


The associated homogenous recurrence relation is


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

Particular solution will be of the form


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

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

Base case is $N(0)=1$



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

Where I am going wrong?

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

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

@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.

However $A(1)=2$ also gives the correct constant value for A.But why not $A(0)=1$?

Related questions

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
49,541 questions
54,083 answers
70,992 users