Write pseudocode to output the nodes in order for the optimal binary search tree given the r(i,j) array (the array that holds the root choices during the construction of the A array). The ordering should be top to bottom, left to right as shown below. Explain that this can be done in O(n) time. Example BST with nodes numbered:

The output should look like: 1,dog 2,cat 3,frog 4,bird 5,cow 6,(empty) 7,goat 8,(empty) 9,(empty) 10,cheetah 11,dingo 12,(empty) 13,(empty) 14,gecko 15,hamster

dog,1 cat,2 frog,3 bird,4 (empty),6 (empty),12 (empty),13 gecko,14 hamster,15 cow,5 goat,7 (empty),8 (empty),9cheetah, 10 dingo,11