Haman wasn't satisfied with all of the wealth, power, descendants, etc., that he had: "all of this is worthless to me as long as Mordechai the Jew sits at the king's gate" (Esther 5:13). So he ended up building the gallows and going to Achashverosh for permission to hang Mordechai, which led to his humiliation and downfall.
This, then, connects with the story of the Tree of Knowledge, where Adam and Chava showed (in a more refined way, granted) the same kind of character flaw: they had an entire garden full of trees to choose from, yet they weren't satisfied until they ate from that one - with consequences that still reverberate today.
Amalek was the first nation to mock Hashem's power - which all of the other nations feared after the Exodus - and attack the Jewish people. This has its roots in Adam's sin, he who was the first to disobey a direct command of Hashem.
Maharsha to Chullin there says that Haman is: (a) a descendant of Eisav and Amalek, the embodiment of the evil represented by the snake in that story; (b) associated with the snake in Bereishis Rabbah 19:2, they being two of four characters in the Torah who started a statement with אף ("also," but also "anger") and whom Hashem punished with anger; and (c) also associated with the snake in Sotah 9b, they being two in a long list of characters who wanted more than they already had and ended up losing it all (similar to the first explanation above, though focusing on the snake's desire for Chava - see Rashi there - rather than on Adam).