I read this book in English some time between 2010 and 2014.
Most of these details are vague in my memory and I may have some of them confused, but to the best of my memory these are the details:
There were two main characters, and unfortunately I don't remember either of their names. The first I remember was a girl who at the beginning of the story was searching for a flying city. If I remember right it flew by using hot air balloons. I'm pretty sure she had been born in the city and maybe even had some memories of it, and that her parents had died or gone missing, which was the reason she was looking for it. She ended up finding it and I believe went through at least one trial to become an accepted member of the society.
The second character I remember was a boy who lived in a ruined city where robot creatures had taken over and had to be avoided. I think he had a little sister. He somehow ended up in an underground fighting ring of sorts, where people would kind of merge minds with their robot creature and fight with them. His dad, who had been missing for some time, was or had been part of this, and the boy learned to do it himself and had a dog-like robot named Spot.
The girl and the boy were connected to each other and to at least two other kids through special books. The books had stories of the other kids in them, seemingly written before the stories themselves had actually taken place in the real world. The boy and girl learned to communicate either through the books or some other means near the end of the story. Also near the end, some evil creature or force became apparent, and I remember the girl either dealing with it somehow or learning about it, maybe sending a warning of some kind.
I liked the book and read it at least twice before returning it to the library, and there was a website for the authors somewhere in the cover that didn't work by the time I had the book. I know it had two authors, and I remember looking for information on a sequel and not being able to find anything at the time. I also seem to remember something about a tree, I'm not sure if it was in the title or on the cover or somehow part of the story.
I've scoured Google with various keywords, but I haven't been able to find it.
Does anyone know this book?