TL;DR On non-rooted devices, where do Android apps store data that survives uninstall?
Backstory: I installed an Android app a couple months ago and configured it to my liking. After a couple weeks, I no longer needed it, so I uninstalled it. After the uninstall, I didn't see any files left behind in Internal Storage, and the device had no microSD card installed, so no files were stored there either.
To my surprise, when I reinstalled the app, it remembered all of it's configurations. I use a firewall, so it didn't download the configurations from the cloud.
Thus, the question: On non-rooted devices, where do Android apps store data that survives an uninstall?