There is only one Deep Sea Tooth in the game, and it's hidden on a small patch of water in Route 20 (just surf east off the southern coast of Cinnabar Island). The exact spot is hidden, so the Dowsing Machine will help but is not required.
Below is a screenshot of the item's exact location.
(Source: Guide Strats)