What in the world are you talking about? Since when does the Constitution have to explicitly confer a right to execute anyone for crimes short of treason? Does it explicitly confer a right to imprison or fine someone for crimes short of treason or for treason itself for that matter? The Constitution doesn't explicitly permit a particular punishment for any particular crime.
Second Congress Sess. I. Ch.7.Probably a lot more death penalty offenses. Search the U.S. Congress from 1789 to 1875 here
1792Sec. 15 And be it further enacted, That if any person or persons shall rob any carrier of the mail of the United States, of such mail, or if any person shall rob the mail, in which letters are sent to be conveyed by post, of any letter or packet, or shall steal such mail, or shall steal and take from or out of the same, or from or out of any post-office, any letter or packet, such offender or offenders shall, on conviction thereof suffer death.