If Ted Cruz wishes to run for the Office of the President of the United States he must provide the documentation CRBA (Consolar Report of Birth Abroad of a Citizen of the United States of America) FS-240 that proves he was made a US citizen by the Department of State.
If Ted Cruz cannot provide this documentation he must then not be permitted to run for President of the United States, under the Constitutional requirement for becoming President being must be born a Citizen of the United States.