title: Java Recursive function behavoir
body: <p>I finished developing a BinaryTree class in Java that builds a Huffman-style binary tree/map to "encode" a phrase into a binary value.</p>
  
  <p>Some of the methods use recursion to populate/traverse the nodes of the tree.  I have a method that encodes a string, say <code>test</code> to <code>01111110001</code>.  In order to encode it, I have a function that maps the path of the tree to the node with that character.  I also have a function that searches the nodes to find the leaf node of that character.</p>
  
  <p>Everything is working fine: the tree is built, I can search and locate nodes, and the mapping works.  When I output the node parameter for the <code>searchNode</code> method, it looks like the code is traversing the tree okay... but it doesn't quit after it finds the node.  It finds it multiple times. I have made a few different variations of the method(s) and I can't get it to quit either traversing the entire tree, or stopping once it finds the node the <strong><em>first time</em></strong>.</p>
  
  <p>I'm wondering why the code won't stop after finding the node the first time, and looking for any suggestions on how to optimize it.</p>
  
  <pre><code>public class BinaryTree {
  
          ---snip ---
  
              /*
               * searchNode
               * Searches nodes for a value
               *
               * @param n Node to start or focus at
               * @param c char character to search for
               * @return Node containing value
               */
              public Node searchNode(Node n, char c) {
                  System.out.println(n);
                  if(n != null) {
                      if(n._char == c) { return n; }
                      if(this.searchNode(n._leftChild, c) != null) {
                          return this.searchNode(n._leftChild, c);
                      }
                      if(this.searchNode(n._rightChild, c) != null) {
                          return this.searchNode(n._rightChild, c);
                      }
                  }
                  return null;
              }
  
  
  
  
  
  
              /*
               * mapPath
               * Maps path with 1s or 0s from root node to
               * node containing char
               *
               * @param n Node to map to
               * @return StringBuilder string of map
               */
              public StringBuilder mapPath(Node n) {
                  if(n == null) { return new StringBuilder(1); }
  
                  StringBuilder sb = new StringBuilder(256);
                  if(n == this._root || n._parent == null) {
                      sb.insert(0, "0");
                      return sb;
                  }
                  Node p = n._parent;
                  while(p != null) {
                      if(p._leftChild == n) {
                          sb.insert(0, "0");
                      } else {
                          if(p._rightChild == n) {
                              sb.insert(0, "1");
                          }
                      }
                      n = p;
                      p = p._parent;
                  }
  
                  return sb;
  
              }
  
  
  
  
              /*
               * encodeString
               * Encodes a string with appropriate binary value
               *
               * @param s String to encode
               * @returns encoded String(Builder)
               */
              public StringBuilder encodeString(String s) {
                  StringBuilder sb = new StringBuilder(s.length() * 10);
                  char[] st = s.toCharArray();
                  for(char stt : st) {
                      sb.append(this.mapPath(this.searchNode(this._root, stt)));
                  }
                  return sb;
              }
  
  
  
  
  
              /**
               * @param args the command line arguments
               */
              public static void main(String[] args) {
                  BinaryTree bt = new BinaryTree(args[0]);
                  bt.buildTree();
                  System.out.println(bt.searchNode(bt._root, args[1].toCharArray()[0]));
                  //System.out.println(bt.encodeString(args[1]));
              }
  
          }
  </code></pre>
  
  <p>The first argument is the phrase or data to encode.  The second argument I am passing is the character to search for so <code>java BinaryTree this\ is\ a\ test a</code> uses "this is a test" for the tree and searches for 'a'.</p>
  
  <p>The tree looks like</p>
  
  <pre><code>      14
      /    \
     6      8
    / \     / \
   s  t    _   5
              / \
             i   3
                / \
               a   2
                  / \
                 h  e
  </code></pre>
  
  <p>When I run <code>java BinaryTree this\ is\ a\ test i</code> I get the following output:</p>
  
  <pre><code>_ - 14[parent=null *root*]
  _ - 6[parent=_ - 14[parent=null *root*]]
  s - 3[parent=_ - 6[parent=_ - 14[parent=null *root*]]]
  null
  null
  t - 3[parent=_ - 6[parent=_ - 14[parent=null *root*]]]
  null
  null
  _ - 8[parent=_ - 14[parent=null *root*]]
    - 3[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
  null
  null
  _ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  _ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  _ - 8[parent=_ - 14[parent=null *root*]]
    - 3[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
  null
  null
  _ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  _ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
  </code></pre>
  
  <p>The output includes the parents of the node to help me visualize the tree while debugging.</p>
  
  <p>You can see that it found the character 'i' 9 times. Yet when it encodes the string/characters it translates fine to 110.</p>