  Let $G=(V,E)$ be an $n$-vertex connected graph of maximum degree $\Delta$.
Given access to $V$ and an oracle that given two vertices $u,v\in V$, returns
the shortest path distance between $u$ and $v$, how many queries are needed to
reconstruct $E$? We give a simple deterministic algorithm to reconstruct trees
using $\Delta n\log_\Delta n+(\Delta+2)n$ distance queries and show that even
randomised algorithms need to use at least $\frac1{200} \Delta n\log_\Delta n$
queries in expectation. The best previous lower bound was an
information-theoretic lower bound of $\Omega(n\log n/\log \log n)$. Our lower
bound also extends to related query models including distance queries for
phylogenetic trees, membership queries for learning partitions and path queries
in directed trees.
  We extend our deterministic algorithm to reconstruct graphs without induced
cycles of length at least $k$ using $O_{\Delta,k}(n\log n)$ queries, which
includes various graph classes of interest such as chordal graphs, permutation
graphs and AT-free graphs. Since the previously best known randomised algorithm
for chordal graphs uses $O_{\Delta}(n\log^2 n)$ queries in expectation, we both
get rid off the randomness and get the optimal dependency in $n$ for chordal
graphs and various other graph classes.
  Finally, we build on an algorithm of Kannan, Mathieu, and Zhou [ICALP, 2015]
to give a randomised algorithm for reconstructing graphs of treelength $k$
using $O_{\Delta,k}(n\log^2n)$ queries in expectation.
