UGCNET CSE December 2022: 25

Question

 

How many different trees are possible with ' $n$ ' nodes?

1. $\mathrm{n}_{-1}$
2. $2^{\mathrm{n}}-1$
3. $2^{\mathrm{n}}$
4. $2^{\mathrm{n}}-\mathrm{n}$

(Option $1 [39397]) 1$
(Option $2 [39398]) 2$
(Option $3[39399]) 3$
(Option $4 [39400]) 4$

Answer Given by Candidate : $2$

Answer 1

We are considering here Binary Tree and we can do it different different values of n  like

n=1  only 1 tree we can form

n=2  only 2 trees with different structure we can form

n=3  we can make 5

n=4 we can make 13 different structure

So after seeing this pattern we can conclude that formula will be 2^n - n which is 4th option.

https://testbook.com/question-answer/how-many-differentbinarytrees-are-poss--6565d4495dd3ec1d46de1158#:~:text=Detailed%20Solution,-Download%20Soln%20PDF&text=As%20an%20example%2C%20when%20'n'%20is%20equal%20to%202,%2D%20n)%20unique%20binary%20tree.