$2.(15$ 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$14\mathrm{.}9($a$)$ on page $401$ of Cormen can be printed as$$k$($k$($d$,$d$),$k$($k$($d$,$d$),$k$($d$,$d$))).$

The procedure OPTIMAL$-$BST on page $405$ returns a$$root$$matrix that represents an optimal binary search tree$$OBST$.$ Write a procedure ROOTY$-$PRINT$$that takes such a$$root$$matrix as its argument, and prints it using the functional notation described above. For example, if ROOTY$-$PRINT$$is given the$$root$$matrix in figure$14\mathrm{.}10$on page $406,$ then it must print$$k$($k$($d$,$d$),$k$($k$($k$($d$,$d$),$d$),$d$)).$ The$$BST$$corresponding to this matrix is also shown in figure$14\mathrm{.}9($b$)$ on page $401.$

ROOTY$-$PRINT$$need not print subscripts $($like $).$ It 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. Hint: use ideas from equation $14\mathrm{.}14$ on page $404.$