Just returned from a trip that covered more or less the same route and had a great time.
April may be a little early for the east in that there will still be a fair amount of snow around, particularly on the high ground i.e the mountain ranges around the Black Sea, Erzerum, Artvin and Nemrut Daği in the middle of the country. Bear in mind that cities in the east tend to be at a decent altitude. Artvin is 600m above sea level, Kars is 1768m, Erzerum is 1853m. We visited these places in September and it was decidedly chilly out of the sun.
I'm sure Mehmet and a few other Turkish riders will be along shortly to give you more answers
DickyB's Turkish Delights