I'm having problems converting a binary rooted tree to newick format. The full explanation for such a format can be found: http://code.google.com/p/mrsrf/wiki/NewickTree

An example of a newick format would be as follows:

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

the internal node will become the commas while the leaves will be retained.

such trees have internal nodes which will always have 2 children.

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

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

import java.util.Stack;

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 {
        output += root.getSeq();
        return output;
    }

}

}