Fitch Bottom-Up Pass - Small Parsimony: Fitch's Algorithm Step by Step

The bottom-up pass computes a possible state set for every node.

highlighted = computed this step

Work from leaves toward the root

The bottom-up pass visits children before parents. Each internal node compares the Fitch sets of its children.

\text{post-order}:\ \text{children before parent}

The 2 lower internal nodes have disjoint child sets, so they take unions. The root intersects those sets and keeps A.

\text{empty intersection} \Rightarrow \text{union}