You describe two differen things.
1) Folders left behind in the user-accessible part of the storage after you uninstall an app. That does happen, and the best answer is to know which of your apps create such folders and delete them manually. But you can use an app like SD Maid, mentioned above, to try to identify orphaned folders like this.
2) App data being back when you restore an app. Are you certain you don't have Google's option to automatically back up such data turned on? Because if you have its' that, rather than the data remaining in your device's storage, that is behind this.
Personally I'm old school: I always use the system Settings to uninstall apps, never the Play Store, and I always clear the app's data manually before uninstalling. That way there is no possibility of anything being left. But as said above, these "private" data are different from the contents of any folders the app may create in the internal storage or on the SD card.