NIELIT 2017 OCT Scientific Assistant A (IT) - Section B: 20

Question

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

• A. $12$
• B. $13$
• C. $14$
• D. $15$

Answer 1

Since its not mentioned whether the nodes are labelled or not, so taking un-labelled nodes in general,

maximum number of binary trees = 2nCn / n+1 

This gives 14 binary trees which is option C

Answer 2

$\textit{There is one binary tree with one node. }$

$\textit{There are two differently shaped trees with two nodes. }$

$\textit{There are 14 different (shaped) binary trees with four nodes.}$

$\textit{These different trees are shown below.}$

 

Ref: https://courses.cs.duke.edu/fall03/cps100/assign/writtentree/

https://www.geeksforgeeks.org/total-number-of-possible-binary-search-trees-with-n-keys/