You probably should apply removed first.

If we have foo/bar turning into just foo, we need to safely delete the file bar, and safely delete the directory foo, before we can safely create the file called foo.

Also, we should try to apply these in order, starting from the bottom of the tree up.  That way you can avoid doing removeEmptyParents() until the last name scheduled for removal in that directory is removed.

Its not all that hard.  Since removed is a List<String>, and its built during the name traversal, these are already sorted properly.  We just have to keep track of the directory prefix as we walk through the names:

  String last = "";
  for (String r : removed) {
    if (!samePrefix(r, last))
      removeEmptyParents(last);
    ... delete r
    last = r;
  }
  removeEmptyParents(last);

  private boolean isSamePrefix(String a, String b) {
    int as = a.lastIndexOf('/');
    int bs = b.lastIndexOf('/');
    return a.substring(0, as + 1).equals(bs.substring(0, bs + 1));
  }