[FIXED] How to convert a binary tree to a Newick tree using Python?

Issue

I have created a Tree object with the following structure:

class Tree:

    def __init__(self, data=None):
        self.data = data
        self.left_child = None
        self.right_child = None

An instance of this object is:

tree = Tree("A")
tree.left_child = Tree("B")
tree.right_child = Tree("C")
tree.left_child.left_child = Tree("D")
tree.left_child.right_child = Tree("E")
tree.right_child.left_child = Tree("F")
tree.right_child.right_child = Tree("G")

Its Newick format should be ((G,F)C,(E,D)B)A;

How can I convert any instance of Tree object to its Newick format?

Solution

Thanks to Blckknght for his hint.

def to_newick(tree):
    newick = ""
    newick = traverse(tree, newick)
    newick = f"{newick};"
    return newick

def traverse(tree, newick):
    if tree.left_child and not tree.right_child:
        newick = f"(,{traverse(tree.left_child, newick)}){tree.data}"
    elif not tree.left_child and tree.right_child:
        newick = f"({traverse(tree.right_child, newick)},){tree.data}"
    elif tree.left_child and tree.right_child:
        newick = f"({traverse(tree.right_child, newick)},{traverse(tree.left_child, newick)}){tree.data}"
    elif not tree.left_child and not tree.right_child:
        newick = f"{tree.data}"
    else:
        pass
    return newick

Answered By - James Chang