title: Java Recursion and Binary Tree
body: <p>My class has been working on using recursion to create things like the Towers of Hanoi, Fibonacci, and all that fun stuff.  The problem is, I don't really understand everything very well.  I understand the general concept of recursion, but putting it into practice when making a program feels so complicated to me.  I get that it's calling the method over and over typically under it reaches a base case where it exits, but it's hard for me to write code that does what I want it to do.</p>
  
  <p>We are working on binary trees right now.  We are supposed to use some code provided by my professor to split up a tree, then write a recursive method to print out all the paths that the tree contains.  Our input will be something like <code>(a(b()())(c()()))</code> which would be a tree of:</p>
  
  <pre><code> a
  b c
  </code></pre>
  
  <p>b and c would have 0 children below them.  <code>(a)</code> is a possible node, and <code>()</code> would be an empty node which would be the end of that path.  Our goal is to print out all the paths, so for my example, the output would be:</p>
  
  <pre><code>a b
  
  a c
  </code></pre>
  
  <p>The code we are given includes a helper method that we can use to write our recursive method:</p>
  
  <pre><code>public class BinaryTree {
  
  
  public static void main(String[] args) {
      Scanner scan = new Scanner(System.in);
      String tree = scan.nextLine();//correct format : (a()())
      String[] t = splitTree(tree);
      System.out.println(Arrays.toString(t));
  
  }
  public static String[] splitTree(String tree)
  {
      //expected format
      //(node tree tree)
      //0 1 2-x x-(length-2) length-1
      if(tree.length() &lt;= 2)//tree not long enough to process
          return new String[]{tree};
  
      String[] temp = new String[3];
      temp[0] = "" + tree.charAt(1);//grab tree node
      tree = tree.substring(2, tree.length()-1);//remove node and outer paren
      int parenCount = 0;//count of open paren
      int endTreeOne = 0;//end of first tree
      for(int i = 0; i &lt; tree.length(); i++)
      {
          if(tree.charAt(i) == '(')
              parenCount++;
          if(tree.charAt(i) == ')')
              parenCount--;
          if(parenCount == 0)
          {
              endTreeOne = i;
              break;//ends for loop early
          }
      }
      temp[1] = tree.substring(0, endTreeOne+1);//left tree
      temp[2] = tree.substring(endTreeOne+1);//right tree
      return temp;
  }
  </code></pre>
  
  <p>This method basically converts a string of characters like <code>(a(b()())(c()()))</code> and makes them <code>[a, (b()()), (c()())]</code>.  Splitting the tree up basically.</p>
  
  <p>I'm just really not sure how to proceed from here to write my recursive method.  I feel pretty lost honestly (and frustrated as a result).  I think I need to make my method check for if "()" exists, then that is the end of a path.  Would that be my base case to exit out of the loop I'd need?  I'm not sure how to specify which side of the tree to take as well.  If someone can provide any help, tips, or get me on the right train of thought for tackling this, I'd greatly appreciate it.</p>