The talking tree in question (one of the ones from the seeds quest) is a little south of Keara's flying fortress entrance, east of the Red Hammer Tribe teleporter shrine. Flying along the channel south of the harbour, the beach (with the dragon skeletons further in) is the only significant piece of land at ground level, on the left (flying south) as the channel opens up into the goblin area.
The entrance to the hall of echoes is also marked on your map.
