[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1513
  • Last Modified:

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.
0
shakyas1
Asked:
shakyas1
2 Solutions
 
jkmyoungCommented:
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
 
ozoCommented:
a) (2*4)!/(4!(4+1)!)=14
b)
[[A[B[C]]]D]
and
[[A]B[[C]D]]
would be equally optimal
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Tackle projects and never again get stuck behind a technical roadblock.
Join Now