Hash tables and optimal binary search trees

4. (20 points.) It's possible to print binary search trees (BST's) using a functional notation. If K is the key at the root of a BST, L is the result of printing its left subtree, and R is the result of printing its right subtree, then we can print the BST as K(L, R). For example, the BST in figure 15.9 (a) on page 398 is printed like this. k2(ki(do, d), ku(ks(d2, ds), ks(du, ds))) The procedure OPTIMAL-BST on page 402 returns a root matrix that represents an OBST. Write a procedure that takes such a root matrix as its argument, and prints it using the functional notation described above. For example, if your procedure is given the root matrix in figure 15.10 on page 403, then it must print this: kz(ki(do, d), ks(k-ks(d2, ds), da), ds)) Your procedure may call additional helper procedures. It need not print subscripts (like i), but can print ordinary digits (like '1') instead. For full credit, it must work correctly for any root matrix, not just the ones in the examples. You may write your procedure in pseudocode or in a programming language. It may be easier to use a programming language. 4. (20 points.) It's possible to print binary search trees (BST's) using a functional notation. If K is the key at the root of a BST, L is the result of printing its left subtree, and R is the result of printing its right subtree, then we can print the BST as K(L, R). For example, the BST in figure 15.9 (a) on page 398 is printed like this. k2(ki(do, d), ku(ks(d2, ds), ks(du, ds))) The procedure OPTIMAL-BST on page 402 returns a root matrix that represents an OBST. Write a procedure that takes such a root matrix as its argument, and prints it using the functional notation described above. For example, if your procedure is given the root matrix in figure 15.10 on page 403, then it must print this: kz(ki(do, d), ks(k-ks(d2, ds), da), ds)) Your procedure may call additional helper procedures. It need not print subscripts (like i), but can print ordinary digits (like '1') instead. For full credit, it must work correctly for any root matrix, not just the ones in the examples. You may write your procedure in pseudocode or in a programming language. It may be easier to use a programming language