MOTIVATION: Reconstructing unobserved ancestral states of a phylogenetic tree provides insight into the history of evolving systems and is one of the fundamental problems in phylogenetics. For a fixed phylogenetic tree, the most parsimonious ancestral reconstruction - a solution to the small parsimony problem - can be efficiently found using the dynamic programming algorithms of Fitch-Hartigan and Sankoff. Ancestral reconstruction is important in many applications including inferring the routes of metastases in cancer, deriving the transmission history of viruses, determining the direction of cellular differentiation in organismal development, and detecting recombination and horizontal gene transfer in phylogenetic networks. However, most of these applications impose additional RESULTS: We introduce an alternative, polyhedral approach to ancestral reconstruction problems using the AVAILABILITY: Python implementations of the algorithms provided in this work are available at: github.com/raphael-group/tree-labeling-polytope.