He wasn’t stateless. Stateless means no country recognizes you as a citizen. He just faced arrest if he returned. Same as any other fugitive. People seeking asylum still have a country and citizenship. Also he wasn’t facing treason charges. He was charged under the Espionage Act and with theft of government property. There were others in similar situations that faced up to 45 months in prison and Eric Holder was willing to make a deal in 2015.

He basically is on self imposed exile in Russia.