Unrooted binary tree

Conversely, any full rooted binary tree may be transformed into an unrooted binary tree by removing the root node, replacing the path between its two children by a single undirected edge, and suppressing the orientation of the remaining edges in the graph.

If T is an unrooted binary tree, it defines a hierarchical clustering of its leaves: for each edge (u,v) in T there is a cluster consisting of the leaves that are closer to u than to v, and these sets together with the empty set and the set of all leaves form a maximal non-crossing family.

For instance, cladistic methods such as maximum parsimony use as data a set of binary attributes describing features of the species.

These methods seek a tree with the given species as leaves in which the internal nodes are also labeled with features, and attempt to minimize the number of times some feature is present at only one of the two endpoints of an edge in the tree.

[4] Unrooted binary trees are also used to define branch-decompositions of graphs, by forming an unrooted binary tree whose leaves represent the edges of the given graph.

That is, a branch-decomposition may be viewed as a hierarchical clustering of the edges of the graph.

Branch-decompositions and an associated numerical quantity, branch-width, are closely related to treewidth and form the basis for efficient dynamic programming algorithms on graphs.

[5] Because of their applications in hierarchical clustering, the most natural graph enumeration problem on unrooted binary trees is to count the number of trees with n labeled leaves and unlabeled internal nodes.

An unrooted binary tree on n labeled leaves can be formed by connecting the nth leaf to a new node in the middle of any of the edges of an unrooted binary tree on n − 1 labeled leaves.

Thus, the number of trees on n labeled leaves is the double factorial The numbers of trees on 2, 3, 4, 5, ... labeled leaves are The leaf-to-leaf path-length on a fixed Unrooted Binary Tree (UBT) T encodes the number of edges belonging to the unique path in T connecting a given leaf to another leaf.

For example, by referring to the UBT shown in the image on the right, the path-length sequence from the leaf 1 is

Daniele Catanzaro, Raffaele Pesenti and Laurence Wolsey showed[7] that the path-length sequence collection encoding a given UBT with n leaves must satisfy specific equalities, namely These equalities are proved to be necessary and independent for a path-length collection to encode an UBT with n leaves.