According to the Bible he was crucified on a cross. (Since crucified is the verb for cross, that's a tautology, but you get the idea.)
Occasionally a poet or a hymn writer will use "tree" in a poetic sense, but that's not what the Book says.
A tree, in order to fulfil the curse Deut 21:22-23
"And if a man have committed a sin worthy of death, and he be to be put to death, and thou hang him on a tree:
His body shall not remain all night upon the tree, but thou shalt in any wise bury him that day; (for he that is hanged is accursed of God;) that thy land be not defiled, which the Lord thy God giveth thee for an inheritance."
Gal 3:13 Christ redeemed us from the curse of the Law, having become a curse for us--for it is written, "CURSED IS EVERYONE WHO HANGS ON A TREE
The greatest punishment someone could suffer under civil law, and God's law was to be hung on a tree, this is because not only is it an execution but also a form of pubic humiliation. In Gods law it reflects the disobedience/sin we committed by eating from the tree of knowledge and the affect of shame and death as a result.
This is why God knew that he had to be hung on a tree, in order to cover our ultimate sin and shame which kept us from everlasting life.
Joshua also hung enemies on trees for the very reason of execution and public shaming.
Josh 8:229 He hanged the king of Ai on a tree until evening; and at sunset Joshua gave command and they took his body down from the tree and threw it at the entrance of the city gate, and raised over it a great heap of stones that stands to this day.
Josh 10:26 So afterward Joshua struck them and put them to death, and he hanged them on five trees; and they hung on the trees until evening
Confirming this is :-
Acts 10:39 "whom they slew and hanged on a tree"
Acts 5:30 "Jesus, whom ye slew and hanged on a tree"
Acts 13:29 "they took him down from the tree"
1 Peter 2:24 "who his own self bare our sins in his own body on the tree"
An old question, but recently revived so I shall add what (we believe to be) it actually was.
People on the way to crucifixion were required to pick up and carry the crosspiece of the cross, not the whole thing, just a big wooden pole.
We do not know if their wrists were actually nailed to the pole at that point or later.
At the end of their walk to execution, the pole they were carrying was nailed to some upright wooden "thing" - might have been a tree, or another bigger pole.
"Tree" in the bible is also a convenient translation for any big wooden thingy.
Not a nice way to die.