¿La desinstalación de aplicaciones dejará restos de archivos en el Root (subsistema de Android)?

No en el sistema de archivos interno, pero puede dejar archivos en la tarjeta SD.

Las aplicaciones en Android sólo pueden escribir en dos lugares dentro del sistema de archivos

• /data/data/<packagename>
• /mnt/sdcard/ o /sdcard

El /data/data/<packagename> se elimina cuando se borra la aplicación, por lo que el único lugar donde se puede encontrar el archivo cruft es la tarjeta SD.

Eso depende, muchos desarrolladores no cuidan adecuadamente los datos de sus aplicaciones asociadas y pueden dejarlos por ahí. El gestor de paquetes desinstala las aplicaciones de /data/data/..../ dependiendo del nombre del paquete.

Por ejemplo, la aplicación MyFooBarApp cuyo nombre de paquete es org.foo.bar.app entonces este sería el lugar - /data/data/org.foo.bar.app/ que tendría lo siguiente:

/data/data/org.foo.bar.app/
      |
      +- databases/
      |
      +- lib/
      |
      +- shared_prefs/
      |
      +- cache/
      | 
      +- files/

Esos cinco subdirectorios son marcadores de posición estándar para que las aplicaciones funcionen. Y Package Manager sólo eliminará esos archivos y subdirectorios al desinstalar dicha aplicación.

Con demasiada frecuencia, por retrospectiva o por mal código, las aplicaciones no limpiaban automáticamente después de sí mismas, por ejemplo, colocando archivos temporales en el /sdcard o, por el amor de Dios, en /data/local/tmp lo cual, por cierto, es el peor abuso de la misma, ¡ya que es mundialmente escribible!