The label assigned to the root node of a binary tree uniquely determines the tree shape. This property arises because tree isomorphism algorithms rely on similar node labeling schemes, ensuring a bijective mapping between positive integers and unique tree shapes where each tree shape corresponds to exactly one integer label and vice versa. [@colijn_metric_2018]
Definitions
Synthesis
The related concepts collectively establish that a systematic node labeling scheme can uniquely characterize binary tree topology through the label assigned to the root node, creating a bijective mapping between labels and tree shapes that enables formal comparison via tree isomorphism. This labeling framework provides the mechanistic foundation for metrics that quantify distances between tree shapes, where similarity is determined by the extent to which trees share identically-labeled subtrees, allowing the metric to effectively group trees generated by the same stochastic evolutionary process while distinguishing those from different processes. The approach proves particularly powerful because different generative models—including birth-death processes, Yule models, and Aldous models—leave distinctive topological signatures encoded in structural features like tree asymmetry and cherry frequency, which the node-label-based metric can detect more effectively than simpler summary statistics like tree imbalance alone. However, the sources do not fully resolve how sensitive this labeling approach is to different tree characteristics or whether certain evolutionary scenarios might produce convergent topological patterns that confound discrimination between generative processes.
Related
- Tree asymmetry relates to frequency of symmetric cherry subtrees
- Phylogenetic metrics distinguish trees from different generative processes
- Metric on tree shapes groups phylogenetically similar trees