recategorized by
14,496 views
9 votes
9 votes

How many different trees are there with four nodes $\text{A, B, C}$ and $\text{D}?$

  1. $30$
  2. $60$
  3. $90$
  4. $120$
recategorized by

9 Answers

Best answer
12 votes
12 votes
selected by
14 votes
14 votes

Answer (D)

Below trees are possible if the tree has four nodes

These trees are for unlabeled nodes. Since we have a trees with labels, so each tree in the above diagram, can

be permuted with labels. Since there are four labels (A, B, C, D), so tree can be permuted 4! times.

So there are total of 5 trees possible and each of it can be permuted 4! times.

Therefore total trees possible would be

5 x 4! = 5! = 120

7 votes
7 votes

I think all options are wrong !

In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^{n-2}.

So here 4^(4-2) i.e. 16.

Reference :-

https://en.wikipedia.org/wiki/Cayley's_formula

2 votes
2 votes

1.No of different rooted unlabeled binary tree with n nodes =catalan no=C(2n,n)/n+1 

2.No of different rooted labeled binary tree with n nodes =(C(2n,n)/n+1) *n!

3.No of spanning tree of complete graph with n nodes=No of unrooted labeled tree with n nodes=caley formula=n^n-2

4.No of rooted tree with n nodes=n*(no of unrooted labeled tree with n nodes)=n^n-1

So, answers to the above question will depend upon whether we need a rooted or unrooted labeled tree with n nodes

1.rooted=4^2=16

2.unrooted=4^3=64

both are not in option.

References

https://en.wikipedia.org/wiki/Cayley%27s_formula

https://gateoverflow.in/25231/no-of-different-rooted-labeled-trees-with-n-vertices

http://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

edited by

Related questions

4 votes
4 votes
5 answers
2
go_editor asked Jul 1, 2016
5,928 views
Consider the following binary search tree T given below: Which node contains the fourth smallest element in T?QVWX
5 votes
5 votes
5 answers
3
7 votes
7 votes
2 answers
4
go_editor asked Jul 1, 2016
3,675 views
Let $\text{A}$ be a finite set having $x$ elements and let $\text{B}$ be a finite set having $y$ elements. What is the number of distinct functions mapping $\text{B}$ int...