Would the Joint Comprehensive Plan of Action be considered a treaty or an executive agreement? I understand that in order for a treaty to be considered, the president must seek the approval of the Senate. However, how is the Iran deal a treaty?
It is treated as an executive agreement, not as an Article II "treaty".
Furthermore, it is a "sole executive agreement" instead of a "congressional-executive agreement" as Congressional action is not necessary for it to be implemented -- all the actions that the US needs to take under the deal are things that the President already has authority to do by himself.
Based on information from Brythan in this answer to a different Politics.SE question, I have learned that the JCPOA is neither a Treaty nor an Executive Agreement. This point was emphasized in a letter to the US Congress from the US State Department which clarified that the JCPOA was considered a non-binding Political Agreement, and specifically was not an Executive Agreement. The Wikipedia article on the JCPOA also notes that there has been widespread confusion about this fact, with it being commonly and erroneously reported as an Executive Agreement in various news outlets.
For additional detail on the differences between Treaties, Executive Agreements and Political Commitments I would recommend this article (referenced by the Wikipedia page linked above) which gives a reasonably non-technical and thorough review.