# First try without saving $a0 on the stack.

# C code:
# main () {
#    inorder(root)
# }
#
# void inorder(n) {
#    if (n != null) then {
#       inorder(n.left); 
#       print n.value; 
#       inorder(n.right);
#    }
# }

# Tree nodes:
# struct Node {
#    int value,
#    Node* left,
#    Node* right,
# }
	
# Tree:	
# A (100)
# |   	
# | --------- B (50)
# |   	      |
# |   	      |------- D (20)
# |   	      |
# |   	      |--------E (61)
# |
# | --------- C (120)
# |   	      |
# |   	      |------- F (111)
#
#
	        .data
A:		.word 100
		.word B
		.word C
B:		.word 50
		.word D
		.word E
C:		.word 120
		.word F
		.word 0
D:		.word 20
		.word 0
		.word 0
E:		.word 61
		.word 0
		.word 0
F:		.word 111
		.word 0
		.word 0

root:		.word A
		
nl:            .asciiz "\n"
	
                .text
                .globl main
main:           # BEGIN main prologue
                subu       $sp,$sp, 24           # Allocate stack frame
                sw         $fp, 0($sp)           # Save $fp in frame
                addu       $fp, $sp, 24          # Set up $fp
                sw         $ra, -20($fp)         # Save $ra
                # END main prologue
	
                # CALL inorder(root)
                lw         $a0, root              
                jal        inorder
	
                # BEGIN main epilogue
                lw         $ra, -20($fp)         # Restore $ra
                lw         $fp, -24($fp)         # Restore $fp
                addu       $sp, $sp, 24          # Pop stack frame
                jr         $ra
                # END main epilogue
        
inorder:	# BEGIN fact prologue
                subu       $sp, $sp, 24          # Allocate stack frame
                sw         $fp, 0($sp)           # Save $fp
                addu       $fp, $sp, 24          # Set up $fp
                sw         $ra, -20($fp)         # Save return address
                sw         $a0, -16($fp)         # Save arg 0 (n)
                # END fact prologue

		beqz       $a0, done             # if n==null goto done
	
		lw         $a0, 4($a0)           # n = n.left
		jal        inorder               # call inorder(n.left)
	
		lw         $a0, -16($fp)         # reload n
		lw         $a0,($a0)             # n = n.value
		li         $v0,1                 # print n
		syscall
		li         $v0,4                 # print nl
		la         $a0,nl
		syscall

		lw         $a0, -16($fp)         # reload n
		lw         $a0, 8($a0)           # n = n.right
		jal        inorder               # inorder(n.right)
	
done:	        # BEGIN fact epilogue
                lw         $ra, -20($fp)         # restore $ra
                lw         $fp, -24($fp)         # restore $fp
                addu       $sp, $sp, 24          # pop stack frame
                jr         $ra
                # END fact epilogue