Aug. 7, 2012, midnight by Rosalind Team

**Topics**:
Phylogeny

## Paths in Trees

For any two nodes of a tree, a unique path connects the nodes; more specifically, there is a unique path connecting any pair of leaves. Why must this be the case? If more than one path connected two nodes, then they would necessarily form a cycle, which would violate the definition of tree.

The uniqueness of paths connecting nodes in a tree is helpful in phylogenetic analysis because a rudimentary measure of the separation between two taxa is the distance between them in the tree, which is equal to the number of edges on the unique path connecting the two leaves corresponding to the taxa.

Newick format is a way of representing trees even more concisely than using an adjacency list, especially when dealing with trees whose internal nodes have not been labeled.

First, consider the case of a rooted tree

A number of variations of Newick format exist. First, if a node is not labeled in

A second variation of Newick format occurs when

Note that there will be a large number of different ways to represent

Given: A collection of

Return: A collection of

(cat)dog; dog cat (dog,cat); dog cat

1 2