ISRO-DEC2017-28

Question

The number of structurally different possible binary trees with $4$ nodes is 

• A. $14$
• B. $12$
• C. $336$
• D. $168$

Comments

here strucally differents means not laballed ?

i ticked 336 :( some one verify

---

14

pls verify

---

it should be 14,

no. of structurally different binary binary trees $\equiv$ no. of different unlabeled trees = nth catalan no.

---

it should be 14 as no of structurally different binary trees could be derived through catalan's number.

https://en.wikipedia.org/wiki/Catalan_number

Answer 1

• structurally different  trees = Unlabeled trees 
• Number of Unlabeled binary trees = (2n)!/(n+1)!n!  [Catalan Number]
  • Here n =4
  • answer = 8!/(5! 4!) =14

Answer 2

No of unlabelled binary trees on n nodes = $\frac{_{n}^{2n}\textrm{C}}{n+1}$

No of labelled binary trees on n nodes = $\left ( \frac{_{n}^{2n}\textrm{C}}{n+1} \right )*n!$

Structurally different = unlabelled = $\frac{_{4}^{8}\textrm{C}}{5}$ = $14$