A central problem in molecular systematics is the reconstruction of the evolutionary relationships between organisms, starting from an alignment of DNA sequences. Pictorially and mathematically, these evolutionary relationships are captured by certain graphs, the phylogenetic trees. Tree reconstruction methods are often judged by their accuracy, measured by how “close” they get to the true tree. Yet most reconstruction methods, such as maximum likelihood (ML), do not explicitly maximize this accuracy.   To address this problem, we propose a Bayesian solution.  Given tree samples, we propose finding the tree estimate which is closest on average to the samples. This “median” tree is known as the Bayes estimator (BE).  The BE literally maximizes posterior expected accuracy, measured in terms of closeness (distance) to the true tree.  We discuss a unified framework of BE trees, focusing especially on tree distances which are expressible as squared Euclidean distances. Notable examples include Robinson--Foulds distance, quartet distance, and squared path difference.  Using simulated data, we show Bayes estimators can be efficiently computed in practice by hill climbing.  We also show that Bayes estimators achieve higher accuracy, compared to ML and the popular neighbor-joining method.