converting a Tree to newick format. java
<p>I'm having problems converting a binary rooted tree to newick format.
The full explanation for such a format can be found: <a href="http://code.google.com/p/mrsrf/wiki/NewickTree" rel="nofollow">http://code.google.com/p/mrsrf/wiki/NewickTree</a></p>

<p>An example of a newick format would be as follows:</p>

<p>for a tree T such as <a href="http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic8/images/completetreetwo.gif" rel="nofollow">http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic8/images/completetreetwo.gif</a>
the newick representation would be: (((8,9),(10,11)),((12,13),(14,15)))</p>

<p>the internal node will become the commas while the leaves will be retained.</p>

<p>such trees have internal nodes which will always have 2 children.</p>

<p>I have a problem using recursion to come out with this newick format.
The output contains far too many nodes and braces.</p>

<p>Any comments to resolve this problem is appreciated or even an iterative algorithm would be welcomed</p>

<p><code>
import java.util.Stack;</p>

<p>public class Tree {</p>

<p>....</p>

<pre>public String inOrderNewick(Node root, String output) throws ItemNotFoundException {
    if (root.hasChild()) {
        output += "(";
        output += inOrderNewick(root.child1, output);
        output += ",";
        output += inOrderNewick(root.child2, output);
        output += ")";
        return output;
    } else {
        return root.getSeq();
    }    
</code></pre>

<p>}</p>

<p> 
//edit: implemented the change as advised.
but the desired output for a tree is ((S3,(S1,S2)),(S4,S5))
where the actual output is (((S3,((S3,(S1,S2)),(((S3,((S3,(S1,S2)),(S4,S5))</p>

<p>This tells me that there are logic errors.
Perhaps there is a need to have flags?</p>
