1. (10 marks) Recall the optimal binary search tree algorithm we saw in class that minimizes the expected weight of the tree. Lets define a weight balanced tree as a binary tree such that at every non-leaf node, v, the number of nodes in each of its subtrees is at least one quarter of the total number of nodes in the subtree NOT INCLUDING THE root v. Modify the optimal binary search tree algorithm such that the resulting tree is a weight balanced tree. That is, the optimization has to be limited to weight balanced trees