That's a hard question. What I can say for certain is that the Persians had a thriving culture of vast gardens in their court cities from as early as the Achaemanids. The older Persian word for this 'Pairidaeza' and the tradition of Shahs inviting subjects and courtiers to walk with them in these gardens as signs of favor, led to the modern use of 'paradise' as an analogy for heaven.

I can't speak for earlier than that, and it's spotty how much these gardens were intended for public use since they were initially made for the King and court much like Versailles.