Possible solution: binary search to find the number of hops (buffering intermediate responses so that you don't have to re-send them), and send all missing TTLs

Possible solution: binary search to find the number of hops (buffering intermediate responses so that you don't have to re-send them), and send all missing TTLs in parallel once you've determined the number of hops to use. You could do a linear scan in parallel with the binary search so that the user-facing behavior looks more or less the same as now. (It could be that some utilities---including this one!!!---already do that. The linked article doesn't go into that level of detail and I haven't read the code.)