Why did Frodo feel he had to leave Middle Earth at the of ROTK?

[Lotrelf]

Originally Posted by Inziladun

The darkness wasn't permanent, though. It left no lasting damage in the Blessed Realm.

One final question- What about the Trees, did they ever recover? If not, how can the effects of Morgoth's darkness be said temporary?

Another question just popped in: In The Silmarillion, at one point, Professor says that whenever Elves were to give any message or something by Valar they were given dreams or visions. In LotR, Frodo often sees visions or dreams. His Elvish nature is also the reason he leaves for the Undying Lands. Is there any connection?