Made Easy test series DS

Question

Consider a binary tree where for every node ⏐P – Q⏐ ≤ 2. P represents number of nodes in left sub tree for node S and Q represents the number of nodes in right sub tree for node S for h > 0. The minimum number of nodes present in such binary tree of height h = 4 _________. (Assume root is at height 0)

Comments

It is nothing but minimum number of nodes in a AVL tree

 $T(n)=T(n-1)+T(n-2)+1 , T(0)=1,T(1)=2$

$T(2)=T(1)+T(0)+1=2+1+1=4$

$T(3)=T(2)+T(1)+1=4+2+1=7$

$T(4)=T(3)+T(2)+1=7+4+1=12$ is the answer

---

in AVL tree max difference left subtree and right subtree can be -1,0,+1...logic of AVL is there but not AVL

---

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!

---

Similar question: https://gateoverflow.in/3811/gate2005-it-50

https://gateoverflow.in/117248/balanced-tree-minimum-no-of-nodes-for-height-h

Answer 1

9 is right answer.

Comments

I thiink its 8 no need of 1 node in 1st level of left subtree of right node of degree 2

---

@abhishekmehta4u @Arjun @srestha Can someone please tell me why one extra node in right sub tree and what should be correct answer ? 9 or 8? I am getting 8 

---

it is not satisfying the condition for 1 and 0 , hence i think 9 may be correct

Answer 2

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

Comments

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? 

---

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

---

@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$?

---

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

---

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² * N(H-2) - 2 -1

        = 2² * ( 2 * N(H-3)  - 1 ) - 2 - 1 = 2³ * ( N(H-3) )  - 2²  - 2 - 1

after K iterations,

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

        = 2^K * ( N(H-K) )  - ( 2^(K-1) + .....  + 2²  + 2 + 2⁰ )

        = 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 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

---

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?

---

Mam, it is not AVL tree...

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

---

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

---

That means Catalan number will satisfy 1st formula

right?

---

Mam,How Catalan number will equal to the formula?

---

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?

---

@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

---

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

---

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

---

is root satisfying the given condition ?

---

got it. thanks .

---

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

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

---

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$?

---

First I was confused that empty tree has height $0$ by looking at the best answer from this question on stackoverflow: https://stackoverflow.com/questions/2209777/what-is-the-definition-for-the-height-of-a-tree/2209840#2209840

Later from comments I understood that height of an empty tree is either undefined or $-1$ but definitely not $0$.

The height of an empty tree is not defined.

Source: https://xlinux.nist.gov/dads/HTML/height.html

Conventionally, an empty tree (tree with no nodes, if such are allowed) has height $−1$.

Source: https://en.wikipedia.org/wiki/Tree_(data_structure)