How many different trees are there with four nodes A,B,C and D?

.How many different trees are there with four nodes A,B,C and D?

  1. 30
  2. 60
  3. 90
  4. 120
9Comments
Sumit Verma @sumitkgp
25 Apr 2017 12:52 pm

The question is not clear. Is it asking for binary trees?

shweta @shweta1920
25 Apr 2017 12:57 pm

WELL its a question of ISRO2014 .. i just copied nd paste... so question is same as in ISRO question paper...

shivani @shivani1234
25 Apr 2017 04:18 pm
  • you can solve this question by, initially considering nodes as unlabeled , then by catalan rule no. of trees =2nCn/(n+1)  , and remember if no. of nodes is m then in catalan no. we put n=m-1.
  • Put n=3 , we will get 5 trees
  • now , as we know these nodes are labeled so we start arranging (permuting) them on these 5 trees.
  • so , ans =4! * 5=24*5=120.
shweta @shweta1920
25 Apr 2017 04:54 pm

that rule is for binary tree i guess..

Sumit Verma @sumitkgp
25 Apr 2017 04:33 pm

@shivanijaiswal1234 I am not getting your answer.
 Why Catalan rule? Can you draw 5 tree skeletons ?
Can you explain it with more details ?

Sumit Verma @sumitkgp
25 Apr 2017 04:37 pm

@shweta1920 @shivanijaiswal1234
I think that if nothing is given we can go with the structural definition of tree.
So number of trees will be nn-2
Read this,
http://www-math.mit.edu/~djk/18.310/18.310F04/counting_trees.html

shivani @shivani1234
25 Apr 2017 05:40 pm

yes, i assumed it to be binary tree, as if it would be n-ary tree then 4! *42  then no option is matching 

Sumit Verma @sumitkgp
25 Apr 2017 05:47 pm

In case of binay tree, answer will be 336.

shweta @shweta1920
28 Apr 2017 09:20 pm

ye question ... ny smjh ara .. ;(