#ACE_Test_Series

Question

Consider the following instance of OBST (Optimal Binary search Tree) problem.

N = 4; <$a_1$, $a_2$, $a_3$, $a_4$> = <do, if, int, while>

P(1...4) = <3,3,1,1>; Q(0...4) = <2,3,1,1,1>

The cost of OBST is________.

Comments

@MiNiPanda Yes, the valid answer range given is 32, 32.

---

Okay then.. @Ashwani Kumar 2 please share your approach

---

We need to find a binary search tree for which total cost search is optimal i.e minimum.

$P(1...4) = <3,3,1,1>$

$Q(0...4) = <2,3,1,1,1>$

P is for successful search of key nodes and Q is for unsuccessful search of dummy nodes(which are not present in tree).

Cost=$1*3+2*3+2*1+3*1(successful \ search)+ 2*2+2*3+2*1+3*1+3*1(unsuccessful \ search)$

Cost=$32$