The paper introduces a special case of the Euclidean distance matrix completion problem of interest in statistical data analysis where only the minimal spanning tree distances are given and the matrix completion must preserve the minimal spanning tree. A guided random search algorithm is shown to outperform more standard optimization methods which also force peculiar and generally unwanted geometric structure on the point configurations their completions produce.