data structure in tree

Question

https://gateoverflow.in/?qa=blob&qa_blobid=960122342133549347

Answer 1

We have to strict to structure of tree given.

So, First of all any one can be root so 9C1 ways

Now i m taking example of 1 as root(Rest will be 2,3,4,5,6,7,8,9)

So, Case-1 In left subtree of root 2,3,4 can only be there as per condition

These can be settled in 3! ways

and right subtree  can have 5,6,7,8,9

Now again choose one of 5 for to be root of right subtree of Orignal root

so 5C1 ways

Lets Say Root is 5

Now here again Left side can have either 6 or 9

so 2 ways...

Now Lets say it have 6 as Left Child..So  Right side will have 7,8,9.. SO 3! ways..

Case-2 When 7,8,9 will be at Left Side of 1..

Same story will repeat..

So for 1 as a root we got 2*3!*5C1*2*3!=720

Now we can have 9 different roots so 9c1*720=6480

Comments

Just one confusion in ur explanation ,

Now Lets say it have 6 as Left Child..So  Right side will have 7,8,9.. SO 3! ways..

when u took 5 as the root of right subtree and 6 as its left child then , so then 7 and 8 could be the left and right child of node 6 and 9 could become the right child of 5, is there any issue in it ?