Why did the genie turn Julanar into a tree and not the brigands who raped her? I would think trapping the brigands in the desert forever in tree form as a punishment for their crime would make a lot more sense.

Unfortunately, that's rather consistent with the mythology of otherworldly beings - the person being saved is often saved at the cost of something along the lines of "having a body and soul".

Heck, one interpretation of the tale of Medusa was that she was granted the power to never be raped again (and this interpretation is why safe houses for women in ancient Greece were marked with Medusa's head)

That being said, as far as I know, it's possible this was the only way to save her. Perhaps the Djinni didn't have the power to turn *all* of the bandits into trees. Perhaps the Djinni's magic went awry. Perhaps it was a way to save Julanar from herself (since self-harm is a possible response to being raped.) Perhaps the Djinni legitimately thought that was the appropriate response and wouldn't understand why it would suck for a human to undergo such a fate. Who knows?

If Djinn are anything like Faeries, they can't be trusted to act according to human ideas of right and wrong.

And as far as I know, Djinn are quite a bit like Faeries.

That's not an unfair comparison, as far as I know.