Conventional (that is, without capabilities) traceroute and ping were setuid root because it there was no provision for emitting ICMP packets in the network APIs and only root could assemble raw packets.

The particular way traceroute runs is implementation-defined. Some use ICMP echo request packets (ping), which you have to be root to send on most Unices. Most of them, however, use UDP packets instead.