Somewhat surprisingly, the yesod ha-mizbe’ah – the foundation of the altar – is found only on the Northern and Western sides. The Eastern and Southern sides had no yesod.
Rabbi Elazar explains that this is because that area of the altar did not fall in the area belonging to the tribe of Binyamin, rather it was in the area belonging to the tribe of Yehudah. Rav Shmuel bar Yitzhak explains that this is because oneamah (=cubit) of the altar cut into the area that belonged to the tribe of Yehudah.
A quick review of a map indicates that Jerusalem was split between the tribes of Yehudah (to the south) and Binyamin (to the north). The Gemara in Masechet Yoma (12a) teaches that there is a disagreement between the Tanna Kamma (=first) who believes that Jerusalem was a separate entity – that it was not divided between the shevatim and Rabbi Yehudah who argues that Jerusalem was divided. According to this opinion the border between Yehudah and Binyamin ran through the Temple itself, with the Temple Mount offices on Yehudah’s side and the sanctuary and Holy of Holies on Binyamin’s. A baraita that is brought describes how there was also a “panhandle” of sorts that encroached northward and included the area of the altar within the official boundaries of shevet Yehudah.
The Si’ah Yitzhak explains that all opinions agree that the area where the city of Jerusalem was built had originally been split between Yehudah and Binyamin. The disagreement between the tanna’im is whether when the decision was made to make Jerusalem the spiritual center of the Jewish people the entire city became a separate entity, or perhaps Jerusalem remained within the confines of the two shevatim, and only the area of the Temple itself had extraterritorial status.
Our Gemara suggests that the altar was not entirely within the boundaries of shevet Yehudah, rather it was in shevetBinyamin, with the exception of the south-eastern corner that was in Yehudah. Even so, the Gemara relates a tradition that Binyamin himself “saw” (apparently in a prophetic vision) that the altar — or a significant part of it — would not be in his portion, and was so disturbed by this that as a consolation prize he became the host (ushpizikhan) to the Almighty in that the Holy of Holies was built in his portion.