Although Russian is widely understood all across Eastern Europe, you may want not to use it when travelling there. Russian was taught in schools as the language of the dominant power of the Cold War.

Some people in Eastern Europe will resent your adressing them in Russian. To make a hypothetical comparison, if Germany had invaded England during WW2 and forced people to learn German. Then, a few years later, if a non-German tourist comes to visit England and tries to address people in German, he might not get the warm welcome he should, even if people did understand the language.