During development, multipotent cells differentiate through a hierarchy of increasingly restricted progenitor cell types until they realize specialized cell types. A cell differentiation map describes this hierarchy, and inferring these maps is a key challenge in developmental biology. Recent high-throughput single-cell lineage tracing technologies profile lineages and cell types at scale, but lack the resolution to observe the cell type transitions of individual dividing cells. We introduce a formal definition of a cell differentiation map as well as a quantity, the discrepancy, that measures the fit of a map with observed single-cell lineage tracing data. We further develop an algorithm, Carta, that infers an optimal cell differentiation map from single-cell lineage tracing data, balancing the trade-off between the complexity of the cell differentiation map and the discrepancy with the observed data.