Binary Tree DS

Question

How many distinct binary tree can be formed with three distinct keys?

Please help me to find the correct answer?

Answer 1

This is based on standard result also known as Catalan number :

a) Number of BSTs(binary search trees in which position of keys matter) = Number of unlabelled binary trees of n vertices

                                                                                                          = ²ⁿC_n / (n+1)..

    As in the case of labelled binary trees , the order of keys do not matter , so they can be arranged in any way                                                                                                So number of binary trees = Number of unlabelled binary trees of n vertices * n!

                                                                                                           =  ²ⁿC_n / (n+1) * n!

    Here  n  =  3,

    So , number of labelled binary trees                                                   = ( ⁶C₃ / 4 ) * 3!

                                                                                                           = 5 * 6

                                                                                                           = 30

   Hence 30 should be the correct answer.. 

Comments

Thanks Habib sir...

Answer 2

Just in sir's answer, about labelled and unlabelled binary trees.