Following a plant-based diet while traveling is possible. Planning provisions ahead is important, a lot of the places may not have specialty items. Nutritional yeast, miso, dried legumes, quality wholegrain flour, flax seeds and B12 supplements, are especially hard to find.
Buying a large supply of shelf-stable tofu is always a good idea; it's a product that is high in protein and low in calories, that can be used to make sauces and sautees, while providing calcium (makes sure it has calcium sulfate or calcium chloride in the ingredients list). For iodine, carry iodized salt, or seaweed (wakame or nori). Other essentials, like omega 6 (LA, linoleic acid), can be found in pumpkin seeds, sunflower seeds for instance, omega 3 (ALA, alpha-linoleic acid) can be found in linseed and chia seeds (about 1 tbsp a day).
Staples like nut milks and oats are found everywhere, varying in price and quality. There will always be fresh vegetables available, but the selection can be poor at times. Carrying cans and and dried version of those foods can help, for example: canned and dried potatoes. Canned spinach may not be appealing, but in a place where there are no leafy greens available, it's better than not having any at all. Canned is not ideal, because it has a lot of added ingredients like salt and sugar, but if you plan in advance you can buy brands that have little additives.
Eating frozen, can help in a bind, a lot of frozen vegetables don't lose their nutrients, like Brocoli for instance. Most places will carry frozen goods, and it's generally cheaper than buying the same item fresh. If like us, you lack a fridge, get a bag with insulation or a cooler and keep it in there with other frozen goods. It won't keep forever, but it helps to slow the thawing process.