See the optimal binary search tree algorithm above. 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.

OPTIMAL-BST(p, q.n) and root[l..n. 1..n be new tables 2 fori -1 to n1 4 5 for - 1 to n for i 1 to n-1 + 1 10 for r = i to j 12 13 14 15 return e and root OPTIMAL-BST(p, q.n) and root[l..n. 1..n be new tables 2 fori -1 to n1 4 5 for - 1 to n for i 1 to n-1 + 1 10 for r = i to j 12 13 14 15 return e and root