title: Search a Binary Tree using Recursion in MIPS
body: <p>I need to write a section of code (the Search function) for the following binary tree search.</p>
  <p>An pseudo-code example is given and reads :</p>
  <pre><code>The code for search could look like:
  call store_path
  ##           if (value == 1)
  ##             return 1
  ##           if (left tree exists)
  ##             if (search(left tree, depth+1))
  ##              return 1
  ##           if (right tree exists)
  ##             return search(right tree, depth+1)
  ##           return 0
  </code></pre>
  <p>The whole MIPS code follows :</p>
  <pre><code>    .text       
          .globl __start 
  __start:        # execution starts here
  
      la $a0,tree
      li $a1,0
      jal search  # search the tree
  
      jal print_path  # print the path
              # to the node with val=1
      li $v0,10
      syscall     # au revoir....
  
  
  #------------------------------------------------
  # store_path - store pointer at level n in the path
  #   a0 - holds pointer to string
  #   a1 - level to use in path
  #------------------------------------------------
  store_path:
      sll $t0,$a1,2   # each pointer is 4 bytes
      sw $a0,path($t0)# save pointer to the name
      addi $t0,$t0,4  # make the next entry 
      sw $0,path($t0) #  equal to 0.
      jr $ra
  
  
  #------------------------------------------------
  # print_path() - print the items stored in path 
  #------------------------------------------------
  print_path:
          li $t0,0        # i 
          sll $t1,$t0,2   # each pointer is 4 bytes
          lw $a0,path($t1)
  next:   li $v0,4    
          syscall         # print path[i]
          addi $t0,$t0,1  # i++
          sll $t1,$t0,2   # each pointer is 4 bytes
          lw $a0,path($t1)
          beqz $a0,done
          move $t1,$a0
          la $a0,arrow
          li $v0,4
          syscall         # print &quot;--&gt;&quot;
          move $a0,$t1
          b next
  done:   la $a0,endl
          li $v0,4
          syscall         # print newline
          jr $ra
  path:   .space 80
  
  tree:   .word name0, node1, node2, 0
  node1:  .word name1, node3, node4, 0
  node2:  .word name2, node5, node6, 0
  node3:  .word name3, node7, 0, 0
  node4:  .word name4, node8, node9, 0
  node5:  .word name5, 0, 0, 0
  node6:  .word name6, node10, node11, 0
  node7:  .word name7, 0, 0, 0
  node8:  .word name8, 0, 0, 0
  node9:  .word name9, node12, node13, 0
  node10: .word name10, 0, 0, 0
  node11: .word name11, 0, 0, 0
  node12: .word name12, node14, node15, 0
  node13: .word name13, 0, 0, 0
  node14: .word name14, 0, 0, 1
  node15: .word name15, node16, node17, 0
  node16: .word name16, 0, 0, 0
  node17: .word name17, 0, 0, 0
  
  name0:  .asciiz &quot;apple&quot;
  name1:  .asciiz &quot;orange&quot;
  name2:  .asciiz &quot;bananna&quot;
  name3:  .asciiz &quot;pear&quot;
  name4:  .asciiz &quot;plum&quot;
  name5:  .asciiz &quot;peach&quot;
  name6:  .asciiz &quot;nectarine&quot;
  name7:  .asciiz &quot;pineapple&quot;
  name8:  .asciiz &quot;grapefruit&quot;
  name9:  .asciiz &quot;grape&quot;
  name10: .asciiz &quot;melon&quot;
  name11: .asciiz &quot;avocado&quot;
  name12: .asciiz &quot;star&quot;
  name13: .asciiz &quot;mango&quot;
  name14: .asciiz &quot;passion&quot;
  name15: .asciiz &quot;cantaloupe&quot;
  name16: .asciiz &quot;watermelon&quot;
  name17: .asciiz &quot;apricot&quot;
      
  endl:   .asciiz &quot;\n&quot;
  arrow:  .asciiz &quot;--&gt;&quot;
  </code></pre>
  <p>I have begun writing the Search Function :</p>
  <pre><code>jal store_path
        li $v0, 1
        beq $a0, 1, print_path
  </code></pre>
  <p>Any tips or tricks on how to implement the +1 depth and left and right tree searches would be greatly appreciated!</p>