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 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, soy beans, chia seeds etc.
Staples like nut milks and oats are found everywhere, varying in price and quality. It is sometimes difficult to find nut milk without added sugar or flavorings. There will always be fresh vegetables available, but the selection can be poor at times. Carrying a dried version of those foods can help, for example: dried mushrooms, radish, seaweed, tomatoes etc. Drying your own fresh is even better, it is a good way to keep fruits while on long passages, but only possible in places with a lot of sun and not too much humidity.
Eating frozen produce can help in a bind. A lot of frozen vegetables don't lose their nutrients, like broccoli 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.
Read more about plant based nutrition.