  We study the problem of learning a node-labeled tree given independent traces
from an appropriately defined deletion channel. This problem, tree trace
reconstruction, generalizes string trace reconstruction, which corresponds to
the tree being a path. For many classes of trees, including complete trees and
spiders, we provide algorithms that reconstruct the labels using only a
polynomial number of traces. This exhibits a stark contrast to known results on
string trace reconstruction, which require exponentially many traces, and where
a central open problem is to determine whether a polynomial number of traces
suffice. Our techniques combine novel combinatorial and complex analytic
methods.
