Completeness spanning trees
In a triangle-free graph, a completeness tree must be a Hamiltonian cycle (minus one of its edges). ISGCI says Hamiltonian cycle is NP-complete in triangle-free graphs. Therefore, so is finding a completeness tree (regardless of any restriction on max number of leaves).