En un teléfono no rooteado, las aplicaciones se ejecutan como usuarios distintos y no tienen acceso a archivos creados por otros usuarios o archivos del sistema, es decir, están 'aisladas'. Ya que no pueden realizar tales cambios, diría que lo único que pueden dejar atrás es un poco de detritus en tu tarjeta SD.
En un teléfono rooteado, una aplicación a la que se le ha concedido acceso de root puede hacer prácticamente cualquier cosa que sea posible en el hardware. Las aplicaciones que tienen permisos de root pueden escribir en medios de almacenamiento no solo de lectura (incluida la modificación del cargador de arranque), modificar los datos privados de otros programas, modificar la configuración del sistema, modificar archivos del sistema, etc. Una aplicación rooteada también puede ocultarse del sistema y pretender estar desinstalada mientras sigue perfectamente activa.
Básicamente, las aplicaciones rooteadas pueden hacer cualquier cosa que permita el hardware
Actualizado para incluir la información de Lie Ryan sobre aplicaciones rooteadas.