Instructions

In this homework you will write a program to generate a preorder traversal of a binary search tree from given inorder and postorder traversals using MIPS. It is highly recommended that you first write a C version.

Input

The input will consist of three lines. The first line will include a single integer k indicating the number of items. The second line will consist of k integers for the inorder traversal of a binary search tree. The third line will consist of k integers for the postorder traversal of a binary search tree. For example, for a binary search tree with the structure

        3       
       / \      
      2   4     
     /          
    1           

The input would be

4       
1 2 3 4 
1 2 4 3 

Output

The output will consist of one single line with k integers representing the preorder traversal of the binary search tree.

For example the output of the program given the input above would be

3 2 1 4

Execution

We will test your program using MARS. Do not write code for real MIPS architectures. To test your program, you can use shell commands to execute the program. For Linux systems, the command would be

$ java -jar Mars.jar <source file name>

Otherwise you can choose to use the GUI provided by Mars. We would have covered this in labs so refer to your lab instructions.

Submission

Checkout

Checkout the homework from gradebot.

$ git clone metastasis@gradebot.org:user/{username}/3/3

Check in

You should check in only one file, preorder.s. Any other file found will result in a score of zero.

To check in, make a commit and execute

$ git push origin master

Last Modified: Mar 10, 2017