If we take the Early Medieval period to be from about 500 to 1000 CE, there were various types of housing in Scotland. There was an abundance of loose stone in Scotland resulting from glacier action in the last ice age. When the glaciers retreated, moraine was littered all over the country. In certain places, the type of rock also lent itself easily to splitting into slab-like sections.
There were stone brochs (a type of structure found only in Scotland) that consisted of high circular double-walled towers in drystone building techniques with stairs in the hollow walls to access higher wooden-floored levels. The best preserved of these brochs is the Mousa Broch in Shetland.
Other habitations were crannogs. These were artificial islands built in lochs (the Scottish word for lakes) which supported circular wooden houses with thatched conical roofs and had plank bridges or causeways for access from the shore. Although the first crannogs were very old, crannogs were still in use well into the early Middle Ages.
But generally, houses were usually built of stone, with cavity walls filled with earth, topped with peat or turf that supported timber-framed thatched roofs. These were known as black houses. One side of the house was dedicated to animals, the other side was the living quarters.
Mud huts would definitely not have been a good idea in Scotland with its wet climate. It is possible that in certain areas turf or peat squares might have been used, but generally stone or wood would have been used for the walls.
Early medieval society in Scotland was not tribal or primitive. Scotland was Christianized early, starting from the 5th century. The Picts were just as civilised as people on the European continent and Pictish carvings (cross slabs) show a very high degree of artistic representation. Their clothing and weaponry was the same as that to be found across Europe. The Picts were also highly skilled metalworkers
However, in the Middle Ages, there are reports of houses in cities being built using wood rather than stone. Here is a detailed report on that, although a lot of it is speculation based on English sources rather than Scottish ones: