Put brain into thinking about population density for a moment. NB & NS have quite a bit of crown land, PEI very little. Every place the Walmarts make their stop & park, spend money here policy so very visible they invite a fight from small campgrounds. So, act accoringly. PEI has some wild places, but go with care. I once went walking with my dogs on PEI and wound up on someone's woodlot & got well told off. He later apologized, I apologized for 'us' & believe it or not I run into this person on just about every trip to PEI. Parking by the stream is illegal in NS too.
All three of those provinces were among the first colonies on the continent. There are cow path roads to prove that. All of these I find very interesting. I wouldn't dream of going to those three provinces without some back roads cruising. But somebody is bound to have some 'interest' or 'ownership' in much of it. On PEI there seems to be a road every 1.6 miles (3km). Watch the PEI gov printed
maps for the 'scenic road' icon. I love these. & the fish icon.
Now the island of Newfoundland has less than 500,000 population, so of course there are places. But there is the grr by private campground owners too. Cgs tend to be priced lower too.
Instead of cow paths, you have logging roads. When driving these, watch the tracks of other wheeled vehicles. & look out if these suddenly narrow down to those of large quads (says one who once kept going - an adrenalin trip that one, especially over one bridge).
Remember, you are the visitor.