In the Androids/Cell Saga, when Trunks traveled back in time, he changed history and created a parallel universe.
But Cell also traveled back in time, and apparently arrived before Trunks was and responsible for changes in history, too.
One would think that Trunks would arrive in a parallel universe without a future Cell (in essence, one that was exactly the same as his, up until the point where he arrived.)
Why did Trunks arrive in the same parallel universe as Cell?
Parallel universes can often mess with your mind if you're not careful. You need to pay careful attention to both where you are, what are the possibilities, and what has occurred to affect change. DBZ uses the alternate timeline version of time travel, so this means that many universes can exist, shown or not. A diagram will be easiest.
There are actually 4 different timelines involved in the Cell/Trunks/Android Saga (excluding ones created/changed by time travel).
The first timeline is one in which the Androids have ravaged the earth, and cause chaos. All of the main heroes have died, and Trunks (I'm calling him Trunks "killed") is left to fend for himself. He travels back in time to an alternate DBZ timeline (one we don't see or know much about, but there is only 1 version of Cell in this timeline) to give Goku the medicine. Presumably, he defeats the androids and/or give Goku the medicine, then travels back to his own timeline. At this point, he (Trunks "killed") is killed by Cell (who is the main Cell in the series), and Cell (main) steals his time machine to travel back in time.
Cell (main), travels to the known DBZ timeline from the show. He shows up and that process starts. Trunks (the one called Future Trunks often, the one in the show and in History of Trunks) meanwhile, in his own, future timeline (likely related, see below), also travels back in time, also to the current DBZ known timeline, to warn about the Androids. When he arrives, there are 2 Cells in this timeline, the main one, and one that already existed. The one that is native to this timeline (called Present Cell often), is destroyed with the destruction of the lab by Future Trunks, and Krillin.
Blah, blah, blah. Cell saga continues until Cell (main) is destroyed. At this point, Future Trunks, travels back to his own timeline, and there, already knows about, and destroys the Cell in that timeline (Future Cell). In total, there were:
So why did Trunks arrive in the same Universe as Cell? Well, that's easy. He did, and he didn't. He arrived in the timeline we were shown (the main DBZ continuity), but the previous Trunks arrived in one in which the Future Cell had not arrived yet. The theory of alternate timelines often involves time travel on a single thread. That is, Future Trunks' universe likely existed from a timeline branch in which Cell (main) had already arrived. When Future Trunks traveled back in time, he was traveling to his past, which included Cell (main) being there, but none of the events that had been set into motion to lead to his timeline. His presence then altered the timeline to include the events we saw, and to not include the ones that lead to his time.
Basically, if Trunks didn't go back in time, things could have happened in a way which lead to Trunks going back in time, which caused the series of events in which we saw. Simple, right?
We don't know. Likely something. But we don't have anything to state what might have happened.
There is a much simpler explanation than trying to explain why Cell appeared in Future Trunks timeline in the past, but never emerged/got attention/went completely unknown by Trunks, just so that Future Trunks could travel back and arrive in a past with Cell already existing. And that is: Cell was the one to travel to a time with an already existing time traveler, not Trunks.
It goes like this, there are 4 timelines (that still holds true) and they will be labeled thusly: Original Timeline, Unseen Past Timeline, Series Timeline, New Future Timeline.
Original Timeline: This is the completely unaltered history. Goku dies of the Heart Virus, heroes killed by Androids. Trunks travels into the past (creating the Unseen Timeline) before being killed by Cell. Cell then travels into the past (creating the Series Timeline).
Unseen Timeline: This is the timeline created by Trunks when he went into the past to warn about the Androids. Trunks is the only time traveler here, there is no Cell from the future. We never see this timeline in the series.
Series Timeline: The timeline we see in the series (obviously). This one is created by Cell when he travels into the past. Now, I know what you're thinking. "But Cell went back further than Trunks did so how is Trunks still there?" Because Trunks' arrival is part of the history of the Unseen Timeline. Nothing Cell does in the past will prevent Trunks from appearing. So, Trunks splits along with everyone else, and the entire timeline.
New Future Timeline: The New Future is the final timeline, the one that the Trunks from the Series Timeline inadvertently creates when he returns home. After warning Goku and the others about the Androids Trunks attempts to return home unaware that he's already done so (in the Unseen Timeline) thus causing the Original Timeline to split and form the New Future Timeline. The New Future is the history where Trunks knows of, and kills, Cell.
