Solved

# optimal binary search tree and dynamic programming

Posted on 2006-05-01
1,486 Views
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
Question by:shakyas1

LVL 12

Assisted Solution

Listed in order of inorder traversal (root, left, right)
ABCD
ABDC
ACBD
BACD
CABD
DABC
DACB
DBAC
DCAB
DCBA
14 in all.
0

Author Comment

Thank u for the answer to the first one
how about the answer to the second question.
0

LVL 84

Accepted Solution

a) (2*4)!/(4!(4+1)!)=14
b)
[[A[B[C]]]D]
and
[[A]B[[C]D]]
would be equally optimal
0

## Join & Write a Comment Already a member? Login.

### Suggested Solutions

Title # Comments Views Activity
find distance using springs and slopes 23 111
Stat question 5 74
CAGR Calculation For SIP 13 55
algorithm 15 51
Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethiā¦
This is a research brief on the potential colonization of humans on Mars.
how to add IIS SMTP to handle application/Scanner relays into office 365.
Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filledā¦

#### 728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!