When the position of the root in an evolutionary tree is unknown, we can simply assign the root to any edge that we like, apply SmallParsimony from “Implement SmallParsimony” to the resulting rooted tree, and then remove the root. It can be shown that this method provides a solution to the following problem.

Small Parsimony in an Unrooted Tree Problem

Find the most parsimonious labeling of the internal nodes in an unrooted tree.

Given: An unrooted binary tree with each leaf labeled by a string of length m.

Return: A labeling of all other nodes of the tree by strings of length m that minimizes the parsimony score of the tree.

Note on formatting: Your internal node labelings may differ from the sample provided.