There are some special trees you can headbutt. It's been a while since I played G/S but I think certain trees have rare Pokemon in. They are always in those trees and never in others, I think it's a bit like Feebas being in only 5 tiles in R/S.
So you'd have to try a bunch of trees on the route in question, and once you find one with the rare Pokemon, keep using that tree.
