During the reign of Charlemagne, East Central and Eastern Europe were populated by dozens of small-scale, "pagan" societies organized on the basis of fragile tribal or clan bonds. Two centuries later, around 1000, the picture changed completely.
Now, the region was divided among several kingdoms with Christian rulers and with their own dioceses and rudiments of ecclesiastical organization. Throughout the region, political centralization went hand in hand with Christianization, with one process accelerating the other.
However, both processes were predicated upon intensive and varied interactions that have taken place during the 9th and 10th centuries between local elites, on the one hand, and the Frankish or Byzantine Empire, on the other hand. While Bohemia, Poland and Hungary entered the Frankish geopolitical sphere and through the decision of their respective rulers subsequently became part of Latin Christianity, Rus' adopted Christianity from Byzantium and transformed its liturgy and culture.
All those polities, however, maintained at least some contact with both Western and Eastern Christianity.