Does uninstalling apps leave any traces? I come from a Windows background where anything you install-uninstall usually leaves traces which are sometimes hard to detect and remove.

Does the same happen when you remove Android apps? I know there is no registry in Linux/Android, but is there any place where traces can still remain?

I have seen some apps creating folders on the SD Card, but that's easy to spot and delete.

Thank you.
On an unrooted phone, apps run as distinct users, and don't have access to any files created by other users or system files, i.e. they are 'sandboxed'.  Since they can't make any such changes, I would say the only thing they can leave behind is a little detritus on your SD card.

On a rooted phone, an app which has been granted root access can do pretty much anything that is possible in the hardware. Apps that have root permissions can write on non-read-only storage media (including modifying the bootloader), modify other programs' private data, modify system settings, modify system files, etc. A rooted app can also hide itself from the system, and pretend to be uninstalled while being perfectly well and alive.

Basically, rooted apps can do anything that the hardware allows

Updated to include Lie Ryan's info on rooted apps.