Reconstructing Binary Trees in Parallel
Ramtin Afshar, Michael T. Goodrich, Pedro Matias, Martha Carolina Osegueda · 2020
We study the parallel query complexity of reconstructing binary trees from simple queries involving their nodes. We show that a querier can efficiently reconstruct a binary tree with a logarithmic number of rounds and quasilinear number of queries, with high probability, for various types of queries.