This sounds like a segment from the 4th book of James Clemmens' The Banned and The Banished series. The series was published between 1999 and 2003.
The series is a five book epic centred around the journey of the Wit'ch from childhood innocent to fantasy epic hero with her surrounding band of support heroes freeing the land from the Tyranny of the big bad.
One of the original members of the party is a Tree Spirit called Nee'lahn. Her story through the five books is a redemption arc both personally and for her people.
In Nee'lahn's case, her race are the spirits of a particular type of tree that used to cover most of the continent. In ages past the trees became affected by a Blight...
and started to go bad. The spirits of such contaminated trees become Wraiths and are both terrible and deadly. Nee'lahn has to accept that the original situation where they covered the continent was as bad as the current state of them dying out is, before she's able to find a solution to the problem with the help of her new friends.
In book one Nee'lahn finds the remains of the forests "King" Tree which though a series of co-incidences convinces her to join the Heroic group.
There are what feels like dozens of separate current or remnant fragment civilisations across the land, some human some less so. One of these old kingdoms used to live inside a city carved into a wall (think Petra, but granite) near the forests of the tree nymphs.
Bad Forest King
Also in this forest is a mage, who's experiments have gone badly wrong and turned him and a bunch of his wood carving creations into petrified wood/stone creatures. The mage himself displays a split personality of himself and his first creation that calls himself a "King". The mage lives inside a tree if I recall correctly.
At the end of the 3rd book there's a running battle in a fortified city
Where the heroes aided by a band of Noble pirates, their former slave master mermaids and a Dragon defeat the local overlords/bad wizards. Just in time to realise how much bigger their problems are.
Geopolitical/Epic overtone and mostly book 5 spoilers.
The whole series is framed as "historical documents" by a future civilisation who are keen to restrict the information in them to only a trusted few to ensure the stability of the society.
The saga itself ultimately is all about stopping the big bad before he gains control of all magic and total control of the whole world.