Question: What king of Scots was deposed before an alliance between Scotland and France was signed?

Context paragraphs:
Rough Wooing: The Rough Wooing (December 1543 – March 1551) was a war between Scotland and England.  Following its break with Rome, England decided to attack Scotland, partly to destroy the Auld Alliance, and prevent Scotland being used as a springboard for future invasion by France, partly to weaken Scotland, and partly to force Scotland to agree to a marriage alliance between its child Queen Mary and the English heir apparent Edward, son of King Henry VIII.  An invasion of France was also contemplated.  War was declared by Henry in an attempt to force the Scots to agree to a marriage between Edward and the infant queen, thereby creating a new alliance between Scotland and England.  Edward, crowned king in 1547 at the age of nine, continued the war for a time under the direction of the Duke of Somerset before Somerset's removal from power in 1549 and replacement by the Duke of Northumberland, who wished for a less costly foreign policy than his predecessor.  It was the last major conflict between Scotland and England before the Union of the Crowns in 1603, excepting perhaps the English intervention at the Siege of Leith in 1560, and was part of the Anglo-Scottish Wars of the 16th century.

Mary of Guise: Mary of Guise (French: "Marie de Guise" ; 22 November 1515 – 11 June 1560) was Queen of Scots from 1538 to 1542 as the second wife of King James V.  She was the mother of Mary, Queen of Scots, and served as Regent of Scotland in her daughter's name from 1554 to 1560.  A native of Lorraine, she was a member of the powerful House of Guise, which played a prominent role in 16th-century French politics.  Her main goal was a close alliance between the powerful French Catholic nation and smaller Scotland, which she wanted to be Catholic and independent of England.  She failed, and at her death the Protestants took control of Scotland, with her own grandson achieving the Union of the Crowns a few decades later.

Treaty of Alliance (1778): The Treaty of Alliance with France or Franco-American Treaty was a defensive alliance between France and the United States of America, formed in the midst of the American Revolutionary War, which promised mutual military support in case fighting should break out between French and British forces, as the result signing the previously concluded Treaty of Amity and Commerce.  The alliance was planned to endure indefinitely into the future.  Delegates of King Louis XVI of France and the Second Continental Congress, who represented the United States at this time, signed the two treaties along with a separate and secret clause dealing with future Spanish involvement, at the hôtel de Coislin (4, place de la Concorde) in Paris on February 6, 1778.  The Franco-American alliance that would technically remain in effect until the 1800 Treaty of Mortefontaine, despite being annulled by the United States Congress in 1793 when George Washington gave his Neutrality Proclamation speech saying that America would stay neutral in the French Revolution.

Gille Coluim the Marischal: Gille Coluim the Marischal was an official of the Scottish crown in the second half of the 12th century.  His name occurs in the witness lists of two extant charters, both issued by King William of Scotland at Perth, which indicates that he was probably a native of somewhere in southern Perthshire.  He seems in fact to have been the lord of Madderty in Strathearn.  In either 1172 or 1173 he witnessed King William's grant of Ardross to Merleswain mac Cholbaín, a relative of the mormaer of Fife. ; and somewhere between 1178 and 1185 he witnessed the king's grant of lands in Inverness-shire to Gille Brigte, Mormaer of Strathearn.  In both of these charters, the grants are to native Scots and Gille Coluim appears alongside other native Scots, such as (in both cases) Gille Críst mac ingine Samuel ("Gillecrist mac inien Samüel") and Gille Míchéil mac Donnchada ("Gillemichel mac Dunecan").  Gille Coluim in both cases appears with the title "Marescal", meaning that he was the king's military commander.  It appears to be in this role that Gille Coluim was given control of the castle at Auldearn ("Heryn") in Moray during a rebellion by the Meic Uilleim, a royal kindred who were claiming the throne of Scotland.  A charter issued by King William at Linlithgow, between 1187 and 1189 grants Gille Brigte, mormaer of Strathearn, the land of Madderty and states that neither Gille Coluim nor his heirs have any right to the land after giving up Auldearn to the "Meic Uilleim".  In the charter, King William declares that Gille Coluim "feloniously surrendered my castle of Heryn and then went over to my mortal enemies in the manner of a wicked traitor and stood with them against me to do as much harm as he could".  We can be certain then that Gille Coluim surrendered the castle during the insurrection of Domnall MacUilleim ("Donald MacWilliam") which took place between 1179 and 1187.  Nothing more is heard of Gille Coluim.  The charter indicates that Gille Coluim was not dead at the time of issue (no later than 1190) and his death is not otherwise reported.

John Balliol: John Balliol (  1249 – late 1314), known derisively as "Toom Tabard" (meaning "empty coat") was King of Scots from 1292 to 1296.  Little is known of his early life.  After the death of Margaret, Maid of Norway, Scotland entered an interregnum during which several competitors for the Crown of Scotland put forward claims.  Balliol was chosen from among them as the new King of Scotland by a group of selected noblemen headed by King Edward I of England.  Edward used his influence over the process to subjugate Scotland and undermined Balliol's personal reign by treating Scotland as a vassal of England.  Edward's influence in Scottish affairs tainted Balliol's reign and the Scottish nobility deposed him and appointed a council of twelve to rule instead.  This council signed a treaty with France known as the Auld Alliance.

Saint Margaret of Scotland: Saint Margaret of Scotland (c. 1045 – 16 November 1093), also known as Margaret of Wessex, was an English princess of the House of Wessex.  Margaret was sometimes called "The Pearl of Scotland".  Born in exile in the Kingdom of Hungary, she was the sister of Edgar Ætheling, the shortly reigned and uncrowned Anglo-Saxon King of England.  Margaret and her family returned to the Kingdom of England in 1057, but fled to the Kingdom of Scotland following the Norman conquest of England in 1066.  In 1070 Margaret married King Malcolm III of Scotland, becoming Queen of Scots.  She was a very pious Roman Catholic, and among many charitable works she established a ferry across the Firth of Forth in Scotland for pilgrims travelling to St Andrews in Fife, which gave the towns of South Queensferry and North Queensferry their names.  Margaret was the mother of three kings of Scotland, or four, if Edmund of Scotland, who ruled with his uncle, Donald III, is counted, and of a queen consort of England.  According to the "Vita S. Margaritae (Scotorum) Reginae" ("Life of St. Margaret, Queen (of the Scots)"), attributed to Turgot of Durham, she died at Edinburgh Castle in Edinburgh, Scotland in 1093, merely days after receiving the news of her husband's death in battle.  In 1250 Pope Innocent IV canonized her, and her remains were reinterred in a shrine in Dunfermline Abbey in Fife, Scotland.  Her relics were dispersed after the Scottish Reformation and subsequently lost.  Mary, Queen of Scots at one time owned her head, which was subsequently preserved by Jesuits in the Scottish College, Douai, France, from where it was subsequently lost during the French Revolution.

Treaty of Berwick (1639): The Treaty of Berwick (also known as the Peace of Berwick or the Pacification of Berwick) was signed on 18 June 1639 between England and Scotland.  Archibald Johnston was involved in the negotiations before King Charles was forced to sign the treaty.  The agreement, overall, officially ended the First Bishops' War even though both sides saw it only as a temporary truce.  After the treaty was signed, King Charles immediately began to gather the resources he needed in order to strengthen his armies.  At the beginning of the Second Bishops' War, the agreement was broken.  After a disastrous skirmish at Kelso between the English advance guard and the Scottish Covenanter Army, the Earl of Holland fled back to the king’s headquarters at Berwick-upon-Tweed.  The Earl of Antrim failed to establish negotiations in order to bring the Irish army over.  This, along with the unsuccessful English naval campaign at Hamilton, meant that Charles was forced to sign a truce.  He conceded to the Scots the right to a free church assembly and a free parliament.  These rights were asserted (with the right to keep the existing legal structure instead of a separate parliament) along with the extension to Scotland of The Bill of Rights (which set out the conditions and powers of a monarch) in the Treaty of Union, 1707, which united England and Wales with Scotland.

Royal Banner of Scotland: The Royal Banner of the Royal Arms of Scotland, also known as the Royal Banner of Scotland, or more commonly the Lion Rampant of Scotland, and historically as the Royal Standard of Scotland, (Scottish Gaelic: "Bratach rìoghail na h-Alba" , Scots: "Ryal banner o Scotland" ) or Banner of the King of Scots, is the Royal Banner of Scotland, and historically, the Royal Standard of the Kingdom of Scotland.  Used historically by the King of Scots, the banner differs from Scotland's national flag, the Saltire, in that its correct use is restricted by an Act of the Parliament of Scotland to only a few Great Officers of State who officially represent the Sovereign in Scotland.  It is also used in an official capacity at royal residences in Scotland when the Sovereign is not present.

List of Scottish monarchs: The monarch of Scotland was the head of state of the Kingdom of Scotland.  According to tradition, the first King of Scots (Middle Scots: "King of Scottis", Modern Scots: "King o Scots" Scottish Gaelic: "Rìghrean Albannaich") was Kenneth MacAlpin (Cináed mac Ailpín), who founded the state in 843.  The distinction between the Kingdom of Scotland and the Kingdom of the Picts is rather the product of later medieval myth and confusion from a change in nomenclature i.e. "Rex Pictorum" (King of the Picts) becomes "Rí Alban" (King of Alba) under Donald II when annals switched from Latin to vernacular around the end of the 9th century, by which time the word Alba in Gaelic had come to refer to the Kingdom of the Picts rather than Great Britain (its older meaning).

Auld Alliance: The Auld Alliance (Scots for "Old Alliance"; "Vieille Alliance" in French) was the alliance between the kingdoms of Scotland and France.  The Scots word "auld", meaning "old", has become a partly affectionate term for the periodic alliance between the two countries before the Union of Crowns in 1603, when the Scottish monarch James VI acceded to the throne of England (as James I).

Supporting paragraphs: John Balliol Auld Alliance
Answer: John Balliol