Applied Grand Test 2

Question

Number different of binary search trees  which can be created with the elements {12, 34, 22, 43, 13, 45, 55, 94, 99, 23} with 45 as the root is___.

 

Answer 1

Given Set =  {12, 34, 22, 43, 13, 45, 55, 94, 99, 23}  with 45 as the root 

now make 2 sets ---------→  values less than root node elements ==> {12 , 34, 22 , 43, 13, 23}

                              ---------→ values greater than root node ==> { 55, 94, 99}

As we get size as 6 (values less than 45) and 3 (values greater than 45)

 

Formula to find number of possible binary search trees =     (2n)!

                                                                                                      -------------------------

                                                                                                        (n)! * (n+1)!

for n = 6 ===> (12!  / (6! * 7!) ) ==> 132

for n = 3 ===> (6! / (3! * 4!) ) ==> 5

final answer will be 132 * 5 ==> 660