optimal binary search tree and dynamic programming

2. a) How many binary search trees existe for 4 keys A<B<C<D?
    b) Construct an optimal binary tree via dynamic programming when the frequency for successful search is zero and the frequencies for unsuccessful searches  
        are (3,2,1,1,4).

  plese provide steps.
shakyas1Asked:
Who is Participating?
 
ozoConnect With a Mentor Commented:
a) (2*4)!/(4!(4+1)!)=14
b)
[[A[B[C]]]D]
and
[[A]B[[C]D]]
would be equally optimal
0
 
jkmyoungConnect With a Mentor Commented:
Listed in order of inorder traversal (root, left, right)
ABCD
ABDC
ACBD
ADBC
ADCB
BACD
BADC
CABD
CBAD
DABC
DACB
DBAC
DCAB
DCBA
14 in all.
0
 
shakyas1Author Commented:
Thank u for the answer to the first one
how about the answer to the second question.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.