algorithm design techniques is optimalas demonstrated by the existence of the third tree from this we can see that neither of the obvious solutions works this is initially surprisingsince the problem appears to be very similar to the construction of huffman encoding treewhichas we have already seencan be solved by greedy algorithm construction of an optimal binary search tree is harderbecause the data are not constrained to appear only at the leavesand also because the tree must satisfy the binary search tree property dynamic programming solution follows from two observations once againsuppose we are trying to place the (sortedwords wleft wleft+ wright- wright into binary search tree suppose the optimal binary search tree has wi as the rootwhere left < <right then the left subtree must contain wleft wi- and the right subtree must contain wi+ wright (by the binary search tree propertyfurtherboth of these subtrees must also be optimalsince otherwise they could be replaced by optimal subtreeswhich would give better solution for wleft wright thuswe can write formula for the cost cleft,right of an optimal binary search tree figure may be helpful if left rightthen the cost of the tree is this is the nullptr casewhich we always have for binary search trees otherwisethe root costs pi the left subtree has cost of clefti- relative to its rootand the right subtree has cost of ci+ right relative to its root as figure showseach node in these subtrees is one level deeper from wi than from right their respective rootsso we must add - =left pj and = + pj this gives the formula right - cleftright min pj pj pi clefti- ci+ right left<= <=right = + =left right pj min clefti- ci+ right left<= <=right =left from this equationit is straightforward to write program to compute the cost of the optimal binary search tree as usualthe actual search tree can be maintained by saving the value of that minimizes cleftright the standard recursive routine can be used to print the actual tree wi wleft -wi - figure structure of an optimal binary search tree wi + -wright