In order to move your game from a device to another, you have to synchronize both devices to Google Play Games (for Android), Apple Game Center (iOS) or Spooky Universe (both).
This way, the old device sends your villages to the server, and the new device gets them after sync.
If the game was removed from the old phone and synchronization to any service was not enabled, I am afraid there is no way to recover your game data as they no longer exist.
