Reconstructing a Bounded-Degree Directed Tree Using Path Queries

Zhaosen Wang, Jean Honorio

We present a randomized algorithm for reconstructing directed rooted trees of $n$ nodes and node degree at most $d$, by asking at most $O(dn{\log }^{2}n)$ path queries. Each path query…