Deleting a file or directory requires writing an inode to the disk. If the disk is completely full, there is not room for the deletion record, and the delete attempt will fail with an FS_EFULL error.
It should be sufficient to always ensure that at least one area has room for a deletion record. All deletion records are the same size. Once a deletion record is written, the previous inode entry and all children inodes or constituent data blocks can be removed during garbage collection.