What if Algirdas dies before he marries Uliana of Tver and his son Andrew of Polotsk succeeds as the King of Lithuania, what will happen to Lithuania?
Probably more or less the same as IOTL. AFAIR Andrei was quite competent and ruthless, so he most probably would make some kind of alliance with Poland against the Order, although perhaps not the union. But butterflies can do quite a lot...
He was baptized in Orthodox rite. So what? Vytautas was baptized twice in Catholic rite, by the Teutonic Order in 1383 and by Poles in 1386. It suggests that between those years he returned to pagan ways. Andrei can very well be baptized again in Catholic rite.
However, it is possible that he keeps to the Orthodox faith, is not elected King of Poland only becomes an ally of Poland. Then you will have an Orthodox Lithuania.
If Andrei of Polotsk could take the throne of Lithuania, then it would be forseeable that Louis of Hungary would marry someone else, which could butterfly Jadwiga's existence as we know it, contributing to the growth of the Kingdom of Hungary in the process. A Rurikid Lithuania could have a devastating consequences on the other Baltic states as well.
Actually in this case it might be better if Gediminas is killed off, preventing the Gediminids from becoming dominant in Lithuania.
OK, so I guess the Gediminids would still have to function around, although we could easily get rid of the Jaigellon dynasty.
But wouldn't Andrei of Polotsk actually not exist if Algirdas is killed off already?
In a tl that I made adoptable, I had both Algirdas and Casimir III killed.In this case Algirdas would have to be killed sometime between 1319 (the year Andrei of Polotsk was born) and 1362 (the year the Lithuanians won over the Tatars in the Battle of the Blue Waters).